力扣題目：三數之和

題目解析

解法（排序+雙指針）：

**算法思路：**
本題與兩數之和類似，是?常經典的?試題。
與兩數之和稍微不同的是，題?中要求找到所有「不重復」的三元組。那我們可以利?在兩數之和
那??的雙指針思想，來對我們的暴?枚舉做優化：
i. 先排序；
ii. 然后固定?個數 a ：
iii. 在這個數后?的區間內，使?「雙指針算法」快速找到兩個數之和等于 -a 即可。
但是要注意的是，這道題??需要有「去重」操作~
i. 找到?個結果之后， left 和 right 指針要「跳過重復」的元素；
ii. 當使?完?次雙指針算法之后，固定的 a 也要「跳過重復」的元素。

class Solution {
public:vector<vector<int>> threeSum(vector<int>& nums) {ranges::sort(nums);vector<vector<int>> ans;int n = nums.size();for (int i = 0; i < n - 2; i++) {int x = nums[i];if (i && x == nums[i - 1]) continue; // 跳過重復數字if (x + nums[i + 1] + nums[i + 2] > 0) break; // 優化一if (x + nums[n - 2] + nums[n - 1] < 0) continue; // 優化二int j = i + 1, k = n - 1;while (j < k) {int s = x + nums[j] + nums[k];if (s > 0) {k--;} else if (s < 0) {j++;} else { // 三數之和為 0ans.push_back({x, nums[j], nums[k]});for (j++; j < k && nums[j] == nums[j - 1]; j++); // 跳過重復數字for (k--; k > j && nums[k] == nums[k + 1]; k--); // 跳過重復數字}}}return ans;}
};

哈希解法

兩層for循環就可以確定 a 和b 的數值了，可以使用哈希法來確定 0-(a+b) 是否在 數組里出現過，其實這個思路是正確的，但是我們有一個非常棘手的問題，就是題目中說的不可以包含重復的三元組。

把符合條件的三元組放進vector中，然后再去重，這樣是非常費時的，很容易超時，也是這道題目通過率如此之低的根源所在。

去重的過程不好處理，有很多小細節，如果在面試中很難想到位。

時間復雜度可以做到O(n^2)，但還是比較費時的，因為不好做剪枝操作。

大家可以嘗試使用哈希法寫一寫，就知道其困難的程度了。

哈希法C++代碼:

class Solution {
public:vector<vector<int>> threeSum(vector<int>& nums) {vector<vector<int>> result;sort(nums.begin(), nums.end());// 找出a + b + c = 0// a = nums[i], b = nums[j], c = -(a + b)for (int i = 0; i < nums.size(); i++) {// 排序之后如果第一個元素已經大于零，那么不可能湊成三元組if (nums[i] > 0) {break;}if (i > 0 && nums[i] == nums[i - 1]) { //三元組元素a去重continue;}unordered_set<int> set;for (int j = i + 1; j < nums.size(); j++) {if (j > i + 2&& nums[j] == nums[j-1]&& nums[j-1] == nums[j-2]) { // 三元組元素b去重continue;}int c = 0 - (nums[i] + nums[j]);if (set.find(c) != set.end()) {result.push_back({nums[i], nums[j], c});set.erase(c);// 三元組元素c去重} else {set.insert(nums[j]);}}}return result;}
};

附加Java代碼：

class Solution {public List<List<Integer>> threeSum(int[] nums) {int n = nums.length;Arrays.sort(nums);List<List<Integer>> ans = new ArrayList<List<Integer>>();// 枚舉 afor (int first = 0; first < n; ++first) {// 需要和上一次枚舉的數不相同if (first > 0 && nums[first] == nums[first - 1]) {continue;}// c 對應的指針初始指向數組的最右端int third = n - 1;int target = -nums[first];// 枚舉 bfor (int second = first + 1; second < n; ++second) {// 需要和上一次枚舉的數不相同if (second > first + 1 && nums[second] == nums[second - 1]) {continue;}// 需要保證 b 的指針在 c 的指針的左側while (second < third && nums[second] + nums[third] > target) {--third;}// 如果指針重合，隨著 b 后續的增加// 就不會有滿足 a+b+c=0 并且 b<c 的 c 了，可以退出循環if (second == third) {break;}if (nums[second] + nums[third] == target) {List<Integer> list = new ArrayList<Integer>();list.add(nums[first]);list.add(nums[second]);list.add(nums[third]);ans.add(list);}}}return ans;}
}