LeetCode 15. 3Sum

原题：https://leetcode.com/problems/3sum/
思路：
3Sum的问题其实是2Sum问题的晋级版，可我当年投机取巧用hashmap过了2sum问题（有兴趣可以搜下我的解法^-^），导致这个3sum卡壳了很久。所以经验教训是，不管自己AC了没有，要看看别人怎么做的，歪门邪道不一定次次通用。
因此先来解决下2sum的问题，也就是给定一个数组，找到两个元素a[i],a[j]使得a[i]+a[j]=X的问题，简单点，假设X=0；这个问题可以用两个指针来解决，当然前提是要先把数组排序好，时间复杂度是O(nlogn). 排序后，假设两个指针一开始指向数组的头、末元素(i=0, j=size-1)，然后就有三种可能性：

• 刚好碰巧这两个值的和就是0 ，那么下一步i,j就要各自朝向内部移动一格(i++, j–)。这里不会产生分支情况，即不可能存在a[i]+a[j] == a[i+1]+a[j] 或==a[i]+a[j-1]，除非前项、后项的值是同一个元素；
• 如果两个值的和<0了，那说明负能量太大了，因此i明显太小了，要把i向右移动让它变大才有可能，因此i++；
• 与上一条同理，j–;

所以，2sum问题在排序后，内部查找的时间复杂度是线性复杂度O(n).
那么3sum问题呢，可以先简化一下，假设不用考虑数组内有重复元素的情况，那么可以把3Sum问题这样简化，固定一个位置的元素a[pos]，在数组内寻找另外两个元素，其值a[i]+a[j]==-a[pos]，这就变成2Sum问题了，其中之前提到的X=-a[pos]。整个算法需要先排序一遍，时间复杂度O(nlogn)，然后需要遍历每个pos再在循环里做2Sum问题，复杂度为O(n^2)，所以两个连在一起，复杂度在O(n^2)范围内（暴力解法复杂度为O(n^3)）。
代码（记得处理重复问题）：

bool sortFunc (int i,int j) { return (i<j); }
class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        sort(nums.begin(), nums.end(), sortFunc);
        vector<vector<int>> results;
        for(int pos=0; pos<nums.size(); pos++){
            threeSumSub(nums, pos, results);
            while(pos+1 < nums.size() && nums[pos+1] == nums[pos])
                pos++;
        };
        return results;
    }
    void threeSumSub(vector<int>& nums, int pos, vector<vector<int>> &results) {
        //Find two elements which add up equals -nums[pos]
        int i = pos+1;
        int j = nums.size() - 1;
        int val;
        while(i < j) {
            val = nums[pos] + nums[i] + nums[j];
            if(val == 0){
                vector<int> solution;
                solution.push_back(nums[pos]);
                solution.push_back(nums[i]);
                solution.push_back(nums[j]);
                results.push_back(solution);
                while(nums[i+1] == nums[i] && i < j) i++;
                while(nums[j-1] == nums[j] && i < j) j--;
                i++;
                j--;
            } else if (val < 0) {
                //Too big, move right
                while(nums[i+1] == nums[i] && i < j) i++;
                i++;
            } else {
                while(nums[j-1] == nums[j] && i < j) j--;
                j--;
            }
        }
    }
};