kSUM

leetcode中有几个求sum的问题，思路基本上一样，在这里一并列出。

这几道题主要思路是在使用双指针解决2SUM的基础上，将kSUM逐步reduce到2SUM。 大致框架如下：

1) sort

2) repeatedly reduce kSUM to k-1SUM, until 2SUM

3) solve 2SUM

那么问题就变成了怎样解决2SUM。这里2SUM描述成：

　　　　　　“Given an sorted array of integers, find two numbers such that they add up to a specific target number”

如前所述，解决这个问题要用两个pointer，start和end，分别从数组两边向中间扫描，

if Array[start] + Array[end] > target, end--;

if Array[start] + Array[end] < target, start++;

if Array[start] + Array[end] = target, add Array[start] and Array[end] to the result set;

有时为了去掉重复元素（如 {2,2,3,5}，这里第一个2和第二个2是重复的，有时只需要考虑一个就可以），每次在比较完Array[start] + Array[end]和target的大小后，要分别加上（具体用法见3SUM的code）

while(Array[start - 1] == Array[start] && start < end) start++;

while(Array[end + 1] == Array[end] && end > start) end--;

好了，这几道题的主体思路有了，我们一道一道看。

TWO SUM： https://leetcode.com/problems/two-sum/

这道题和我们在上面描述的2SUM问题有三点不同，第一是这道题输入数组没有排序，第二是这道题需要返回index，第三是这道题不需要去重。

首先我们根据上面的思路来做，先sort。但是由于结果要返回index，所以排序之前先保存一下之前的数组，最后再回来找index。之后再双指针两边扫描。时间上需要O(nlogn)， 空间上需要O(n)。代码如下 

class Solution {
public:
    vector<int> twoSum(vector<int> &numbers, int target) {
        vector<int> ori = numbers;
        sort(numbers.begin(), numbers.end());
        int start = 0, end = numbers.size() - 1;
        while(start < end) {
            if(numbers[start] + numbers[end] < target)
                start++;
            else if(numbers[start] + numbers[end] > target)
                end--;
            else
                break;
        }
        vector<int> res;
        for(int i = 0; i < ori.size(); i++) {
            if(ori[i] == numbers[start] || ori[i] == numbers[end])
                res.push_back(i + 1);
        }
        return res;
    }
};

不过2sum这道题还有一个方法就是用hashtable把所有过往元素都存下来，这样time complexity是O(n)， space也是O(n)，但由于这种方法并不适合用于解决k>=3的问题，这里不做过多的讲解，详细解释可以看leetcode官方给出的solution。代码如下

class Solution {
public:
    vector<int> twoSum(vector<int> &numbers, int target) {
        unordered_map<int, int> visited;
        vector<int> res;
        for(int i = 0; i < numbers.size(); i++) {
            if(visited.find(target - numbers[i]) == visited.end()) {
                visited.insert(make_pair(numbers[i], i));
            }
            else {
                res.push_back(visited[target - numbers[i]] + 1);
                res.push_back(i + 1);
                return res;
            }
        }
        return res;
    }
};

3SUM：https://leetcode.com/problems/3sum/

这道题就是根据之前说的框架，先sort，然后reduce，然后用2SUM处理。这里的reduce很直接了，就是依次把数组中每一个元素值的负值作为2SUM中的target，start每次从当前target元素的下一个开始即可。注意代码中的去重部分。这样子O(n^2)的时间。

class Solution {
public:
    vector<vector<int> > threeSum(vector<int> &num) {
        vector<vector<int> > res;
        sort(num.begin(), num.end());
        int i = 0;
        while(i < num.size()) {
            int target = 0 - num[i];
            int start = i + 1, end = num.size() - 1;
            while(start < end) {
                if(num[start] + num[end] < target) {
                    start++; 
                    //去重
                    while(start < end && num[start - 1] == num[start])
                        start++;
                }
                else if(num[start] + num[end] > target) {
                    end--;
                    //去重
                    while(start < end && num[end + 1] == num[end])
                        end--;
                }
                else {
                    vector<int> re;
                    re.push_back(num[i]);
                    re.push_back(num[start]);
                    re.push_back(num[end]);
                    res.push_back(re);
                    start++;
                    end--;
                    //去重
                    while(start < end && num[start - 1] == num[start])
                        start++;
                    while(start < end && num[end + 1] == num[end])
                        end--;
                }
            }
            i++;
            //去重
            while(i < num.size() && num[i - 1] == num[i])
                i++;
        }
        return res;
    }
};        

3SUM Closest: https://leetcode.com/problems/3sum-closest/

这道题和上一道思路几乎一样，区别是返回的要求不同而已。时间也是O(n^2)。

class Solution {
public:
    int threeSumClosest(vector<int> &num, int target) {
        sort(num.begin(), num.end());
        int close = num[0] + num[1] + num[2];
        int i = 0;
        while(i < num.size()) {
            int start = i + 1, end = num.size() - 1;
            while(start < end) {
                int sum = num[start] + num[end] + num[i];
                close = abs(close - target) < abs(sum - target) ? close : sum;
                if(sum < target) {
                    start++;
                    while(start < end && num[start - 1] == num[start])
                        start++;
                }
                else if(sum > target) {
                    end--;
                    while(start < end && num[end + 1] == num[end])
                        end--;
                }
                else
                    return close;
            }
            i++;
            while(i < num.size() && num[i - 1] == num[i])
                i++;
        }
        return close;
    }
};

4SUM：https://leetcode.com/problems/4sum/

这个系列的最后一道题，但是思路并没有变化，只是需要从4SUM reduce to 2SUM。

class Solution {
public:
    vector<vector<int> > fourSum(vector<int> &num, int target) {
        sort(num.begin(), num.end());
        vector<vector<int> > res;
        for(int i = 0; i < num.size(); i++) {
            for(int j = i + 1; j < num.size(); j++) {
                int start = j + 1, end = num.size() - 1;
                while(start < end) {
                    int sum = num[i] + num[j] + num[start] + num[end];
                    if(sum < target) {
                        start++;
                        while(start < end && num[start - 1] == num[start])
                            start++;
                    }
                    else if(sum > target) {
                        end--;
                        while(start < end && num[end + 1] == num[end])
                            end--;
                    }
                    else {
                        vector<int> re(4,0);
                        re[0] = num[i];
                        re[1] = num[j];
                        re[2] = num[start];
                        re[3] = num[end];
                        res.push_back(re);
                        start++;
                        end--;
                        while(start < end && num[start - 1] == num[start])
                            start++;
                        while(start < end && num[end + 1] == num[end])
                            end--;
                    }
                }
                while(j + 1 < num.size() && num[j] == num[j + 1])
                    j++;
            }
            while(i + 1 < num.size() && num[i] == num[i + 1])
                i++;
        }
        return res;
    }
};

如果kSUM的话，需要使用backtracking。这个问题本身是NP-hard的。

更正：

之前说的基本思路的确是可行的，而且对于kSUM=target, kSUM<target, kSUM>target （比如3SUM closest） 都适用。但是2SUM的hashtable方法在k是偶数的时候可以提高效率，只是需要更多的空间去存储。参考http://westpavilion.blogspot.com/2014/02/k-sum-problem.html的分析。

reference

http://cs.stackexchange.com/questions/2973/generalised-3sum-k-sum-problem

http://blog.csdn.net/linhuanmars/article/details/19711651

http://westpavilion.blogspot.com/2014/02/k-sum-problem.html