傳送門：三數(shù)之和

思路

為了去重，需要先排序。

排序之后，顯然每一個(gè) $nums[i]$ 就可以作為三數(shù)之中的第一個(gè)數(shù)。

因此，對(duì)于每一個(gè) $i$，第二、三個(gè)數(shù)只能在 $[i+1,n]$ 之間取得。

這時(shí)候如果使用 map 去維護(hù)每個(gè) nums 對(duì)應(yīng)的所有下標(biāo)（例如：std::map <int, std::vector<int>> mp;），實(shí)際上還是會(huì)超時(shí)。因?yàn)榧词勾_定了第一、二個(gè)數(shù)，當(dāng)查找第三個(gè)數(shù)時(shí)，哪怕用二分，都還要再乘上一個(gè) $logn$ 的復(fù)雜度。

但這也同時(shí)提醒我們，如果確定了第二、三個(gè)數(shù)，那就可以判斷出 $nums[2]+nums[3]$ 是大于還是小于 $?nums[1]$，這就意味著我們可以通過(guò)移動(dòng) 2、3 指針的方式，來(lái)找到 $nums[2]+nums[3]=?nums[1]$ 的情況。

因此這道題可以用雙指針的方式來(lái)做，還是有點(diǎn)難想的。

還需要額外注意 [… , a , a , …] 和 [ … , a , b , b , … ] 這兩種特殊情況。

代碼

class Solution {
public:vector<vector<int>> threeSum(vector<int>& nums) {std::sort(nums.begin(), nums.end());std::vector<std::vector<int>> result;for (int i = 0; i < nums.size(); ++ i) {int sum = -nums[i];// 防止 a aif (i >= 1 && nums[i] == nums[i - 1]) continue;int r = nums.size() - 1; for (int l = i + 1; l < nums.size(); ++ l) {// 防止 a b bif (l > i + 1 && nums[l] == nums[l - 1]) continue;while (r > l && nums[l] + nums[r] > sum) r--;if (l == r) break;if (nums[l] + nums[r] == sum) {result.push_back({nums[i], nums[l], nums[r]});}}} return result;}
};