KSum

2016-04-25

问题描述

K-Sum问题可以描述为，给定一个未排序且可重复的整数array以及一个target，求是否存在K个array中的整数，使得它们的和为target。找出所有的组合，并且不能重复，每个组合数字按升序排列。

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)

思路

由于要求说明，最后的结果中的每组数字是有序排列的，所以首先想到对整个array进行排序。

时间复杂度: \(\Theta(N\log(N))\)

问题化简

对于2Sum, 可以利用一头一尾的双指针遍历数组，从而找到结果。

i = 0;
j = nums.size() - 1;
while (i < j){
    if (nums[i] + nums[j] == target){
        //save the result
    }
    else if (nums[i] + nums[j] > target){
        j--;
    }
    else{
        i++;
    }
}

以此类推，对于3Sum，可以将其转化为,先取一个数，再求target减去该数的2Sum。4Sum一直到KSum都是，可以转化为求K-1Sum。

对于KSum，暴力解法的时间复杂度是 \(\Theta(N^k)\)。(找出所有K元组再判断)

而经过化简时间复杂度变为： \(\Theta(N\log(N) + N^{k-1}) = \Theta(N^{k-1})\)。

结果去重

题目要求去掉重复的结果，由于前面我们已经将array排好了序，所以对于每次结果我们只需要判断其与前一次结果是否一样，不一样的话才存入结果序列。

对于外重循环，判断当前的值是否等于上次一次的值，若相等则跳过该次循环。

Code of 4Sum

vector<vector<int>> fourSum(vector<int>& nums, int target) {
    vector<vector<int> > res;
    if (nums.size() < 4) return res;
    vector<int> triple(4);
    sort(nums.begin(), nums.end());
    int n = nums.size();
    int i, j ,k, l;
    int prei, prej;
    for (i = 0; i < n-3; i++){
        //去重：与前一次值相等则跳过该次循环
        if (i!=0 && (nums[i] > target || nums[i] == prei)) continue;
        prei = nums[i];
        triple[0] = nums[i];
        for (j = i + 1; j < n -2; j++){
            //去重：与前一次值相等则跳过该次循环
            if (j != i+1 && (nums[j] + nums[i] > target || nums[j] == prej)) continue;
            prej = nums[j];
            triple[1] = nums[j];
            k = j + 1;
            l = n - 1;
            while (l > k){
                triple[2] = nums[k];
                triple[3] = nums[l];
                int sum = triple[0] + triple[1] + triple[2] + triple[3];
                if (target  == sum){
                    if (res.size() == 0){
                        res.push_back(triple);
                    }
                    else if (res.back() != triple){ //去重：与前一次值相等则跳过该结果
                        res.push_back(triple);
                    }
                    ++k;
                    --l;
                }
                else if (target < sum){
                    l--;
                }
                else{
                    k++;
                }
            }
        }
    }
    return res;
}