Leetcode中有很多“N Sum”問題缚陷，這種問題就是給出一個數(shù)組A袒餐，一個目標數(shù)T,然后計算得出在A中有多少數(shù)種的組合嗡呼，使得其和剛好是T.
問題如下：
2 Sum: https://leetcode.com/problems/two-sum/
2 Sum Input array is sorted: https://leetcode.com/problems/two-sum-ii-input-array-is-sorted
3 Sum: https://leetcode.com/problems/3sum
3 sum-closest: https://leetcode.com/problems/3sum-closest/
4 Sum: https://leetcode.com/problems/4sum/
4 SumII: https://leetcode.com/problems/4sum-ii/

首先從最簡單的2 Sum Input array is sorted: 問題來看

Given an array of integers that is already sorted in ascending order, find two numbers such that they add up to a specific target number.

The function twoSum should return indices of the two numbers such that they add up to the target, where index1 must be less than index2. Please note that your returned answers (both index1 and index2) are not zero-based.

You may assume that each input would have exactly one solution and you may not use the same element twice.

Input: numbers={2, 7, 11, 15}, target=9
Output: index1=1, index2=2

由于數(shù)組是已經(jīng)排序的华嘹，那么我們可以知道數(shù)組中最小的數(shù)是nums[0],最大的是nums[nums.size() - 1]场仲。設置兩個index，一個叫front仁热，初始值為0榜揖，另外一個叫back，初始值為nums.size() - 1抗蠢。求nums[front] + nums[back]举哟，如果和大于target，那么就將back減一迅矛，如果小于妨猩，就將front 加1。
將上述思路整理成代碼秽褒。

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        vector<int> res;
        int front = 0;
        int back = nums.size() - 1;
        while(front < back) {
            int t = nums[front] + nums[back] ;
            if(t == target) {
                res.push_back(front + 1);
                res.push_back(back + 1);
                return res;
            }
            else if(t > target) 
                back --;            
            else 
                front ++;
        }
        return res;
    }
};

上述解法復雜度為O(N)壶硅，算是比較理想的解法了。有了這個基礎销斟，我們看下面的題庐椒。
3 Sum

Given an array S of n integers, are there elements a, b, c in S such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero.
Note: The solution set must not contain duplicate triplets.

For example, given array S = [-1, 0, 1, 2, -1, -4],
A solution set is:

[
  [-1, 0, 1],
  [-1, -1, 2]
]

由于我們已經(jīng)做了 2 Sum問題，那么這個題可以轉(zhuǎn)化（下降）為2 Sum問題蚂踊。然后采用上面的算法來做约谈。代碼如下：

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        vector<vector<int>> res;
        sort(nums.begin(), nums.end());//排序
        unsigned int i;
        for (i = 0; i < nums.size(); ++i) {
            int target = -nums[i];//這里轉(zhuǎn)化為了2 Sum問題
            int front = i + 1;
            int back = nums.size() - 1;
            while(front < back) {
                int sum = nums[front] + nums[back];
                if(sum < target) 
                    front++;
                else if(sum > target) 
                    back--;
                else {
                    vector<int> triple(3,0);
                    triple[0] = nums[i];
                    triple[1] = nums[front];
                    triple[2] = nums[back];
                    res.push_back(triple);
                    //跳過相同的數(shù)字
                while(front < back && nums[front]== triple[1])
                    front ++;
                while(front < back && nums[back] == triple[2])
                    back--;
                }
                }
                while(i + 1 < nums.size() && nums[i] == nums[i + 1]) 
                    i++;
            }
        return res;
    }
};

下面的4 Sum問題也可以變?yōu)? Sum然后變?yōu)? Sum來解決。
https://leetcode.com/problems/4sum/#/description

剩下的幾個題比較特殊犁钟，因為不能用排序打亂順序棱诱，這就需要用到hash表來存儲。我留到下次再總結吧特纤。