15. 3Sum
想法
3个for循环的解法肯定是超时的，考虑使用双指针的方法。要特别注意的是不能重复。例如nums = [-1,0,1,2,-1,-4]有2个-1,需要将第二个-1组成的[-1,0,1]剔除。
基本解法
class Solution { public: vector<vector<int>> threeSum(vector<int> &nums) { vector<vector<int>> ans; int N = nums.size(); sort(nums.begin(), nums.end()); for (int first = 0; first < N - 2; first++) { if (nums[first] > 0) { return ans; } // first去重 if (first > 0 && nums[first] == nums[first - 1]) { continue; } int second = first + 1; int third = N - 1; while (second < third) { if (nums[second]+nums[third]>-nums[first]) { third--; } else if (nums[second]+nums[third]<-nums[first]) { second++; } else { ans.push_back({nums[first], nums[second], nums[third]}); second++; third--; // second去重 while (second < third && nums[second] == nums[second - 1]) { second++; } //third去重 while (third > second && nums[third] == nums[third + 1]) { third--; } } } } return ans; } };
这里的双指针是同时滑动的，也就是说比较后2数与首数的大小关系，大于首数说明整体大于0，所以要移动尾指针，反之亦然。这里有一个要注意的点是，当我使用int s = nums[first] + nums[second] + nums[third]，然后比较s与0的大小关系时，总有3个判例超时。后来不写这一步，直接nums[first] + nums[second] + nums[third]与0比较就能通过。就挺离谱的。
