LeetCode 15: 3Sum
写过了2sum，现在再来写3sum，虽然大一下数据结构是写过的orz，应该是写过的，但是某人忘得很彻底。。。没事不迟！

0.回顾一下2sum

在一维array数组里找到两个数（非自身结合），使得两数之和等于target。array和target给定。

• 解决方法：利用哈希，对array从前向后遍历
  • 如果(target-array_i) 在哈希表中搜索false，则将array_i存入哈希表；
  • 如果(target-array_i) 在哈希表中搜索true，OK! return true;

ok来思考3sum

要求

1. 找到所有三元组，三个元素的顺序无所谓，不同组不同内容（数字不一样）；
2. 要求组内元素在array中不同下标；

思路

不重复

1. 对三元组(a,b,c)保证a b c的顺序，避免排列组合类型的重复。于是a≤b≤c，即排序好后，a左 b中 c右；
2. 从小到大遍历a，保证a严格单调递增；
   所以a的严格单调递增保证了(b+c)的严格单调递减,这里就运用双指针的处理方法。

双指针

以此来确定b c具体的值。
在a严格单调递增 and a≤b≤c的条件下，保证b严格单调递增，c严格单调递减。

实现

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        int nsize = nums.size();
        sort(nums.begin(), nums.end());
        vector<vector<int>> ans;
        // enumerate a and make sure that a is strictly monotonically increasing
        for (int first = 0; first < nsize; ++first) {
            // 需要和上一次枚举的数不相同--严格
            if (first > 0 && nums[first] == nums[first - 1])
                continue;
            //第一层for下面 doubly pointer -- second=b third=c
            // c 对应的指针初始指向数组的最右端
            int third = nsize - 1;
            int target = -nums[first];
            // 枚举 b
            for (int second = first + 1; second < nsize; ++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)
                    ans.push_back({nums[first], nums[second], nums[third]});

            }
        }
        return ans;
    }
};