0015-3Sum

#two-pointers #array #sort #grind-169 #neetcode-150

Problem Description

Given an integer array nums, return all the triplets [nums[i], nums[j], nums[k]] such that i != j, i != k, and j != k, and nums[i] + nums[j] + nums[k] == 0.

Notice that the solution set must not contain duplicate triplets.

Solution

核心觀念：先排序，再把 3Sum 降成 2Sum。固定一個數 nums[i]，剩下的問題就是「在 i 右側找兩個數，和為 -nums[i]」——這正是 0167-Two-Sum-II-Input-Array-Is-Sorted 的相向雙指針。外層固定 O(n)、內層雙指針 O(n)，合起來 O(n²)。排序還有一個額外好處：相同的數會相鄰，去重時只要「跳過跟前一個一樣的值」就好，不必另外開 hash set。

nums (sorted): [-4, -1, -1, 0, 1, 2]
                 i   j              k     固定 i=-4，找右側和為 4 → 無
                     i   j       k        固定 i=-1，找右側和為 1 → (0,1) ✔
                         ↑ 下一個 i 也是 -1，和前一個重複 → 跳過，避免重複三元組

方法一：排序 + 雙指針 + 跳過重複 — O(n²)／O(1)（推薦）

// Time: O(n^2)
// Space: O(1)  (不計輸出；排序遞迴堆疊 O(log n) 忽略)
class Solution {
 public:
  vector<vector<int>> threeSum(vector<int>& nums) {
    ranges::sort(nums);
    int n = nums.size();
    vector<vector<int>> ans;
    for (int i = 0; i < n - 2; ++i) {
      if (nums[i] > 0) break;                          // 最小數已 > 0，三數和不可能為 0
      if (i > 0 && nums[i] == nums[i - 1]) continue;   // 跳過重複的 i
      int j = i + 1, k = n - 1;
      while (j < k) {
        int sum = nums[i] + nums[j] + nums[k];
        if (sum == 0) {
          ans.push_back({nums[i], nums[j], nums[k]});
          ++j;
          --k;
          while (j < k && nums[j] == nums[j - 1]) ++j;  // 跳過重複的 j
          while (j < k && nums[k] == nums[k + 1]) --k;  // 跳過重複的 k
        } else if (sum < 0) {
          ++j;
        } else {
          --k;
        }
      }
    }
    return ans;
  }
};

三層去重各自獨立

重複三元組只會從三個地方冒出來，各用一行擋掉：

外層 i：i > 0 && nums[i] == nums[i-1] → continue。同一個最小值只當一次起點。
內層 j、k：找到一組解之後才推進並跳過相同值（while (... nums[j] == nums[j-1]) ++j）。注意要先 ++j; --k; 走一步再比較，否則 nums[j-1] 會指到自己。

這樣全程不需要 hash set，額外空間 O(1)。if (nums[i] > 0) break; 是排序後的剪枝：最小數都正了，後面不可能湊到 0。

方法二：排序 + 雙指針 + hash set 去重 — O(n²)／最壞 O(n²)

你原本的作法：不在指針上跳重複，而是把找到的三元組丟進 unordered_set 自動去重。vector<int> 沒有內建 std::hash，所以要自帶一個 VectorHash（見下方補充）。邏輯比較好寫，但代價是那個 set 幾乎等於把答案再存一份——3Sum 的解最壞有 Θ(n²) 組，額外空間就吃到 O(n²)。

// Time: O(n^2)
// Space: O(t)，t = 三元組數量，最壞 O(n^2)
struct VectorHash {
  size_t operator()(const vector<int>& v) const {
    size_t seed = v.size();
    for (int x : v)
      seed ^= hash<int>{}(x) + 0x9e3779b97f4a7c15ULL + (seed << 6) + (seed >> 2);
    return seed;
  }
};

class Solution {
 public:
  vector<vector<int>> threeSum(vector<int>& nums) {
    ranges::sort(nums);
    int n = nums.size();
    unordered_set<vector<int>, VectorHash> seen;
    for (int i = 0; i < n - 2; ++i) {
      int j = i + 1, k = n - 1;
      while (j < k) {
        int sum = nums[i] + nums[j] + nums[k];
        if (sum == 0) {
          seen.insert({nums[i], nums[j], nums[k]});  // insert 本身就冪等
          ++j;
          --k;
        } else if (sum < 0) {
          ++j;
        } else {
          --k;
        }
      }
    }
    return {seen.begin(), seen.end()};
  }
};

對你原本程式的幾個小建議

if (!mp.contains(...)) mp.insert(...)：多餘。unordered_set::insert 對已存在的 key 本來就不做事，直接 insert 即可，省一次查找。
命中時只 ++j 也會對（最終靠 set 去重），但同時 ++j; --k; 才是雙指針的正解——這組 (j,k) 已用掉，兩邊一起收。
hash 種子常數用 64-bit 的 0x9e3779b97f4a7c15（黃金比例），比 32-bit 的 0x9e3779b9 在 64-bit size_t 上混得更均勻。

補充：vector／pair／tuple 沒有 std::hash，怎麼自己寫

std::hash 只對「純量型別、指標、std::string、std::bitset、std::optional…」這類有特化，容器（vector／array）與 pair／tuple 都沒有，所以 unordered_set<vector<int>>、unordered_map<pair<int,int>, T> 不給自訂 hash 是編不過的。標準作法是用 std::hash<元素型別> 當積木，套 boost::hash_combine 的混合公式：

// 通用：把一個值混進 seed（順序敏感，[1,2] 與 [2,1] 不同 hash）
template <class T>
void hash_combine(size_t& seed, const T& v) {
  seed ^= hash<T>{}(v) + 0x9e3779b97f4a7c15ULL + (seed << 6) + (seed >> 2);
}

struct PairHash {
  template <class A, class B>
  size_t operator()(const pair<A, B>& p) const {
    size_t s = 0; hash_combine(s, p.first); hash_combine(s, p.second); return s;
  }
};
struct TupleHash {
  template <class... Ts>
  size_t operator()(const tuple<Ts...>& t) const {
    size_t s = 0;
    apply([&](const auto&... xs) { (hash_combine(s, xs), ...); }, t);  // C++17 fold
    return s;
  }
};
struct VectorHash {
  template <class T>
  size_t operator()(const vector<T>& v) const {
    size_t s = v.size();
    for (const auto& x : v) hash_combine(s, x);
    return s;
  }
};

// 用法
unordered_set<pair<int, int>, PairHash> a;
unordered_map<tuple<int, int, int>, int, TupleHash> b;
unordered_set<vector<int>, VectorHash> c;

不一定要 hash：有序容器零樣板

如果不是非得 O(1) 不可，直接用有序的 set / map 最省事——vector、pair、tuple 都內建字典序 operator<，所以 set<vector<int>>、map<pair<int,int>, T> 不用寫任何 hash 就能編譯，代價是每次操作 O(log n)。本題若硬要用容器去重，set<vector<int>> 比 unordered_set + VectorHash 少一大段樣板。但最佳解仍是方法一的指針跳重複，連容器都不用開。

0167-Two-Sum-II-Input-Array-Is-Sorted — 本題內層就是在排序陣列上對「兩數和 = -nums[i]」跑相向雙指針
0001-Two-Sum — 最基礎的兩數和；未排序時改用 hash map 換 O(n)
0018-4Sum — 再往外固定一層數，對剩下區間套同一套雙指針，去重邏輯一樣
0011-Container-With-Most-Water — 相向雙指針的另一種應用，靠單調性決定收哪一邊