6.3Sum && 4Sum [ && K sum ]

3Sum

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:

• Elements in a triplet (a,b,c) must be in non-descending order. (ie, a ≤ b ≤ c)
• 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)

 解析：分三步： a.排序.       b. 任取一个没取过的数，余下右边的序列中求 2Sum.       c. 取2Sum的过程中，应保证没有重复。

 4Sum

Given an array S of n integers, are there elements a, b, c, and d in S such that a + b + c + d = target? Find all unique quadruplets in the array which gives the sum of target.

Note:

• Elements in a quadruplet (a,b,c,d) must be in non-descending order. (ie, a ≤ b ≤ c ≤ d)
• The solution set must not contain duplicate quadruplets.

 

    For example, given array S = {1 0 -1 0 -2 2}, and target = 0.

    A solution set is:
    (-1,  0, 0, 1)
    (-2, -1, 1, 2)
    (-2,  0, 0, 2)

 解析：3Sum 之上加一层循环。

 1 class Solution {
 2 public:
 3     vector<vector<int> > fourSum(vector<int> &num, int target) {
 4         vector<vector<int> > vec;
 5         vector<int> ans(4, 0); // record one answer
 6         int n = num.size();
 7         if(n < 4) return vec;
 8         sort(num.begin(), num.end());
 9         int preVal4 = num[0] ^ 0x1;
10         for(int i = 0; i < n - 3; ++i){
11             if(num[i] == preVal4) continue;
12             else preVal4 = num[i];
13             int preVal3 = num[i+1] ^ 0x1;
14             for(int j = i+1; j < n - 2; ++j){
15                 if(num[j] == preVal3) continue;
16                 else preVal3 = num[j];
17                 int s = j + 1, t = n - 1, target2 = target - num[i] - num[j];
18                 while(s < t){
19                     int sum = num[s] + num[t];
20                     if(sum == target2){
21                         ans[0] = num[i]; ans[1] = num[j]; ans[2] = num[s]; ans[3] = num[t];
22                         while(s < t && num[s] == num[s+1]) ++s;
23                         while(s < t && num[t] == num[t-1]) --t;
24                         vec.push_back(ans);
25                         ++s, --t;
26                     }else if(sum < target2) {
27                         ++s;
28                     }else --t;
29                 }
30             }
31         }
32         return vec;
33     }
34 };

Code

kSum(刷题模版)

 1 class Solution {
 2  public:
 3      vector<vector<int> > fourSum(vector<int> &num,int k, int target) {
 4         vector<vector<int> > vec;
 5         vector<int> vec2;
 6         if(num.size() < k) return vec;
 7         sort(num.begin(), num.end());
 8         getSum(vec, vec2, num, 0, k, target);
 9         return vec;
10      }
11  
12      void getSum(vector<vector<int> > &vec, vector<int> &vec2, vector<int> &num, int begin, int k, int target){
13         if(k == 2){
14             int len = num.size(), s = begin, t = len - 1;
15             while(s < t){
16                 int sum = num[s] + num[t];
17                 if(sum == target){
18                     vec2.push_back(num[s]); vec2.push_back(num[t]);
19                     while(s < t && num[s] == num[s+1]) ++s;
20                     while(s < t && num[t] == num[t-1]) --t;
21                     vec.push_back(vec2); 
22                     vec2.pop_back(); vec2.pop_back(); // key 
23                     ++s, --t;
24                 }else if(sum < target) {
25                     ++s;
26                 }else --t;
27             }    
28             
29         }else { 
30             int len = num.size();
31             int preValue = num[begin] ^ 0x1;
32             for(int start = begin; start < len-k+1; ++start){
33                 if(num[start] == preValue) continue;
34                 else preValue = num[start];
35                 vec2.push_back(num[start]);
36                 getSum(vec, vec2, num, start + 1, k - 1, target - num[start]);
37                 vec2.pop_back();
38             }
39         }
40      }
41  };

算法复杂度分析：

k-SUM can be solved more quickly as follows.

• For even k: Compute a sorted list S of all sums of k/2 input elements. Check whether S contains both some number x and its negation ?x. The algorithm runs in O(nk/2logn) time.

• For odd k: Compute the sorted list S of all sums of (k?1)/2 input elements. For each input element a, check whether S contains both x and a?x, for some number x. (The second step is essentially the O(n2)-time algorithm for 3SUM.) The algorithm runs in O(n(k+1)/2) time.

Both algorithms are optimal (except possibly for the log factor when k is even and bigger than 2) for any constant k in a certain weak but natural restriction of the linear decision tree model of computation.

6.3Sum && 4Sum [ && K sum ],布布扣,bubuko.com

6.3Sum && 4Sum [ && K sum ]

原文：http://www.cnblogs.com/liyangguang1988/p/3692540.html