[补题记录]Leetcode 15. 三数之和

传送门：三数之和

思路

为了去重，需要先排序。

排序之后，显然每一个 $nums[i]$ 就可以作为三数之中的第一个数。

因此，对于每一个 $i$，第二、三个数只能在 $[i+1,n]$ 之间取得。

这时候如果使用 map 去维护每个 nums 对应的所有下标（例如：std::map <int, std::vector<int>> mp;），实际上还是会超时。因为即使确定了第一、二个数，当查找第三个数时，哪怕用二分，都还要再乘上一个 $logn$ 的复杂度。

但这也同时提醒我们，如果确定了第二、三个数，那就可以判断出 $nums[2]+nums[3]$ 是大于还是小于 $-nums[1]$，这就意味着我们可以通过移动 2、3 指针的方式，来找到 $nums[2]+nums[3]=-nums[1]$ 的情况。

因此这道题可以用双指针的方式来做，还是有点难想的。

还需要额外注意 [… , 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;}
};