Sum Sum Sum

2019/11/09 LeetCode

本文主要总结一些关于数组求和的编程题目,它们的题目意思很简单也不难理解,但是要解决就需要一些小技巧了。

两数之和

给定一个整数数组以及一个目标值target,要求找到该数组中和为目标值的两个整数,返回它们的数组下标。要求是不能重复使用数组中同样的元素,假设数组中只有唯一解。

最简单的思路是循环遍历数组,将所有的两数组合的和求解出来。但是这样的时间复杂度为,效率不高。一个高效的方法是使用哈希表,首先我们循环一次数组,将每个数a与其下标组成一对关系,我们可以在时间内找到a值在数组中的位置。随后我们再一次遍历数组,寻找target-a在数组中的位置。这两个位置则为最终的答案,这种思路的时间复杂度降低到

由于哈希值的保存需要占用内存空间,所以上面的思路属于经典的时空置换,利用空间来交换时间。例如常见的动态规划就属于时空置换的算法。

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        unordered_map<int, int> m;
        vector<int> res;
        for(int i=0;i<nums.size();i++){
            m[nums[i]]=i;
        }
        for(int i=0;i<nums.size();i++){
            int t = target - nums[i];
            if(m.count(t) && m[t]!=i){
                res.push_back(i);
                res.push_back(m[t]);
                break;
            }
        }
        return res;
    }
};

三数之和

问题升级!现在变为求解出数组中是否存在三个元素使得三数之和等于目标值?你除了要找出所有满足条件的三元组,还要求这些三元组不能重复。例如给定数组nums=[-1,0,1,2,-1,-4],满足要求的三元组有[-1,0,1]以及[-1,-1,2]。

这里给出的思路是三指针法,首先我们需要将给定的数组按照升序排序,得到新的数组。然后从左到右循环遍历数组,假设当前位置为i,那么我们设定两个指针LR。其中指针L指向当前位置的下一个位置,指针R指向数组的最后一个位置。

i、L、R三根指针就绪之后,计算这三个位置的数之和并保存到sum。此时有三种情况需要分类讨论:

  • 如果sum等于目标值,那么将结果保存,更新L、R指针。
  • 如果sum小于目标值,此时将L指针往右边偏移1位,重复该操作。
  • 如果sum大于目标值,此时将R指针往左边偏移1位,重复该操作。

此外还有一个问题需要注意,那就是要避免重复的结果。由于数组已经经过排序处理,所以在更新L、R指针的时候有一个技巧,那就是更新前后位置相同的值则继续偏移。在代码中的体现则是这三个约束条件:

  • nums[i] == nums[i-1]
  • nums[L] == nums[L+1]
  • nums[R] == nums[R-1]

由于指针指向的数值在偏移前后一致的话,会导致最后记录的答案出现重复,所以需要通过上面的三行约束条件来筛除。

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        vector<vector<int>> res;
        sort(nums.begin(), nums.end());
        for(int i=0; i<nums.size(); i++){
            if(nums[i] > 0)
                break;
            if(i>0 && nums[i] == nums[i-1])
                continue;
            int L = i+1;
            int R = nums.size()-1;
            while(L < R){
                int sum = nums[i] + nums[L] + nums[R];
                if(sum == 0){
                    vector<int> temp;
                    temp.push_back(nums[i]);
                    temp.push_back(nums[L]);
                    temp.push_back(nums[R]);
                    res.push_back(temp);
                    while(L<R && nums[L] == nums[L+1])
                        L++;
                    while(L<R && nums[R] == nums[R-1])
                        R--;
                    L++;
                    R--;
                } else if(sum < 0){
                    L++;
                } else if(sum > 0){
                    R--;
                }
            }
        }
        return res;
    }
};

最接近的三数之和

现在需要满足这三数之和与目标值最接近,并求出这三数之和。假定每个数组中只有唯一的答案。

思路依旧是三指针法,改变的地方是在指针偏移的过程中记录下与目标值的差。

class Solution {
public:
    int threeSumClosest(vector<int>& nums, int target) {
        int res = 1000000;
        int kms = 0;
        sort(nums.begin(), nums.end());
        for(int i=0; i<nums.size(); i++){
            if(i>0 && nums[i] == nums[i-1])
                continue;
            int L = i+1;
            int R = nums.size()-1;
            while(L < R){
                int sum = nums[i] + nums[L] + nums[R];
                if(sum == target){
                    return target;
                } else if(sum < target){
                    L++;
                    if(target - sum < res){
                        res = target - sum;
                        kms = sum;
                    }
                } else if(sum > target){
                    R--;
                    if(sum - target < res){
                        res = sum - target;
                        kms = sum;
                    }
                }
            }
        }
        return kms;
    }
};

四数之和

问题继续升级!现在要求求解出等于目标值的四个元素之和,并且输出的四元组不能重复。例如输入的数组为[1, 0, -1, 0, -2, 2],目标值为0,那么输出的四元组有[-1,0,0,1],[-2,-1,1,2],[-2,0,0,2]。

思路上本质还是三指针法,只是再增加一根指针变成四指针。我们用两层循环来遍历数组,i,j指针指向的数值之和相当于是三数之和问题中的第一数。你会注意到当i,j指针确定后,两层循环的内部代码与三指针法是类似的。换汤不换药。

class Solution {
public:
    vector<vector<int>> fourSum(vector<int>& nums, int target) {
        vector<vector<int>> res;
        sort(nums.begin(), nums.end());
        for(int i=0; i<nums.size(); i++){
            if(i>0 && nums[i] == nums[i-1])
                continue;
            for(int j=i+1; j<nums.size(); j++){
                if(j>i+1 && nums[j] == nums[j-1])
                    continue;
                int L = j+1;
                int R = nums.size()-1;
                while(L < R){
                    int sum = nums[i] + nums[j] + nums[L] + nums[R];
                    if(sum == target){
                        vector<int> temp;
                        temp.push_back(nums[i]);
                        temp.push_back(nums[j]);
                        temp.push_back(nums[L]);
                        temp.push_back(nums[R]);
                        res.push_back(temp);
                        while(L<R && nums[L] == nums[L+1])
                            L++;
                        while(L<R && nums[R] == nums[R-1])
                            R--;
                        L++;
                        R--;
                    } else if(sum < target){
                        L++;
                    } else if(sum > target){
                        R--;
                    }
                }
            }
        }
        return res;
    }
};

不限定数之和

给定一个无重复元素的数组和一个目标值,找出这个数组中所有可以使数字之和为目标值的组合。这里的元素可以被重复使用,并且最后的结果不能重复。例如输入的数组为[2,3,5],目标值是8。所有的解集有[2,2,2,2]、[2,3,3]、[3,5]。

这个问题有点像找零钱问题。例如我现在有无数张2元、3元、5元的钞票,我需要凑出8元。那么我先用小额度的开始换,先换2元,一直到剩余0元,或者是这个额度的钞票不满足,换另一个额度。这种思路生成一棵解答树:

以上图为例,每个节点的数值是当前还剩下的值,蓝色的线表示减去2,橙色的线表示减去3,绿色的线表示减去5。黑色的点表示负值,这个时候树的生成就停止了。当节点为0的时候表示已经找到这个组合了,答案就是这条路径上减去的值。例如最左边为0的节点,其路径对应4条蓝色的线,那么答案是[2,2,2,2]。

需要注意了,这样的思路会出现重复解。例如第四层的第2个值为0的节点,这个解是[3,3,2],与第四层的第1个值为0的节点的解重复了。因此我们在生成树的时候需要进行剪枝,图中蓝色虚线的路径需要在生成过程中剪去。这是如何做到的?仔细看一看代码里面的递归函数你就知道了。

class Solution {
public:
    vector<vector<int>> res;
    void func(vector<int>& spe, vector<int>& candidates, int posi, int rest){
        if(rest <= 0){
            if(rest == 0)
                res.push_back(spe);
            return;
        }
        for(int i=posi; i<candidates.size(); i++){
            spe.push_back(candidates[i]);
            func(spe, candidates, i, rest-candidates[i]);
            spe.erase(spe.end()-1);
        }
    }
    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        vector<int> spe;
        func(spe, candidates, 0, target);
        return res;
    }
};

不限定数之和 2

再加点难度。我们现在要求组合中的每个数只能出现一次,怎么求?同样道理,还是使用解答树。只是在剪枝的操作上要稍微变动一点。以上面那题的数据为例,此时的结果只有一个[3,5]。下面是生成的解答树:

这棵解答树在上面的树基础上再增加一个约束条件,那就是每个数只能出现一次,相当于是每一条根节点到叶子节点的路径上出现的颜色不能相同,那些虚线的边就是需要剪去的部分。

在如何处理重复值的问题上,下面的代码给出了新的思路。这个思路跟三指针法处理重复值的思路是一样的。

class Solution {
public:
    vector<vector<int>> res;
    void func(vector<int>& candidates, int rest, int posi, vector<int>& temp){
        if(rest <= 0 || posi == candidates.size()){
            if(rest == 0){
                res.push_back(temp);
            }
            return;
        }
        temp.push_back(candidates[posi]);
        func(candidates, rest-candidates[posi], posi+1, temp);
        temp.erase(temp.end()-1);
        
        while(posi < candidates.size()-1 && candidates[posi+1] == candidates[posi])
            posi++;
        func(candidates, rest, posi+1, temp);
    }
    vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
        if(candidates.size() == 0)
            return res;
        sort(candidates.begin(), candidates.end());
        vector<int> temp;
        func(candidates, target, 0, temp);
        return res;
    }
};

总结

这里总共提及到三个思想,第一种思路是时空平衡,利用哈希将时间转移到空间上。第二种思路是三指针法,不断逼近搜索空间。第三种思路是解答树,并使用回溯的方法找出路径,而且还要正确的剪枝避免重复值。

Search

    Table of Contents