Two sum及其衍生问题

2021-03-06 本文已影响0人小幸运Q

求数值镜像问题可以考虑用hash

Two Sum

Given nums = [2, 7, 11, 15], target = 9,
Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1]

方法1：用哈希表，每遍历到一个元素num，看target-num是否在hash表中，如果在就得出答案，如果不在就将当前num放入哈希表中。复杂度 $O(n)$ （存储开销大）

如果想得到所有的结果，可能需要vector<vector<int>>v;

方法2：如果给定的数组是已排序的数组，那么就可以设定lo和hi两个指针，如果这两个数字的和比target要大，那么就lo++，否则hi--，复杂度 $O(n+nlog_2(n))=O(nlog_2n)$ （排序开销大）

Three Sum：

寻找3个数的和为0的组合：

从头开始每次取一个数作为sum，则此题变成了在后面的数组中寻找两个数其和为-sum，就和上面的过程一样。最终 $O(nlog_2n+n*n)=O(n^2)$

Four Sum

思路一：先遍历第一个数，然后固定第一个数之后，转化为剩下元素的3SUM问题。 $O(n*log_2n+n*nlog_2n)$

（我的思路是从后往前遍历，因为从后往前遍历的点值比较大，而且vector方便从后插入。去重采用的是unordered_map+string）

class Solution {
public:
    static bool cmp(int &i, int &j){
        return i<j;
    }
    vector<vector<int>> twosum(vector<int>nums,int target,int left,int right){
        int i=left;
        int j=right;
        vector<vector<int>>res;
        if(right-left<1){
            return res;
        }
        while(i<j){
            if(nums[i]+nums[j] >target ) {
                j--;
            } else if (nums[i]+nums[j] < target) {
                i++;
            }else{
                vector<int>t;
                t.push_back(nums[i]);
                t.push_back(nums[j]);
                res.push_back(t);
                i++;
            }
        }
        return res;
    }
    vector<vector<int>>threesum(vector<int>&nums,int target,int left,int right){
        int i,j;
        vector<vector<int>>v;
        if(right-left<2){
            return v;
        }
        for(i=right;i>=left+2;i--){
            vector<vector<int>>vv;
            vv=twosum(nums,target-nums[i],left,i-1);
            for(j=0;j<vv.size();j++){
                vv[j].push_back(nums[i]);
                v.push_back(vv[j]);
            }
        }
        return v;
    }
    vector<vector<int>> fourSum(vector<int>& nums, int target) {
        sort(nums.begin(),nums.end(),cmp);
        vector<vector<int>>res;
        int size=nums.size();
        int i,j,k;
        if(size<4){
            return res;
        }
        for(i=size-1;i>2;i--){
            vector<vector<int>>v;
            v=threesum(nums,target-nums[i],0,i-1);
            for (j=0;j<v.size();j++){
                v[j].push_back(nums[i]);
                res.push_back(v[j]);
            }
        }
        vector<vector<int>>Res;
        unordered_map<string,bool>m;
        for(i=0;i<res.size();i++){
            string s="";
            s=to_string(res[i][0])+","+to_string(res[i][1])+","+to_string(res[i][2])+","+to_string(res[i][3]);
            if(m.count(s)){
                
            }else{
                m[s]=true;
                Res.push_back(res[i]);
            }
        }
        return Res;
    }
};

不过理论上不去重也是可以的，在NSum里面用while(){i--};i--;跳过重复的末元素即可，但是似乎效率更低了/迷

class Solution {
public:
    static bool cmp(int &i, int &j){
        return i<j;
    }
    vector<vector<int>> twosum(vector<int>nums,int target,int left,int right){
        int i=left;
        int j=right;
        vector<vector<int>>res;
        if(right-left<1){
            return res;
        }
        while(i<j){
            if(nums[i]+nums[j] >target ) {
                while (i < j && nums[j] == nums[j-1]){
                    j--;
                }
                j--;
            } else if (nums[i]+nums[j] < target) {
                while (i < j && nums[i] == nums[i+1]){
                    i++;
                }
                i++;
            }else{
                vector<int>t;
                t.push_back(nums[i]);
                t.push_back(nums[j]);
                res.push_back(t);

                while (i < j && nums[i] == nums[i+1]){
                    ++i;
                }
                while(i<j && nums[j]==nums[j-1]){
                    --j;
                }
                i++;
            }
        }
        return res;
    }
    vector<vector<int>>threesum(vector<int>&nums,int target,int left,int right){
        int i,j;
        vector<vector<int>>v;
        if(right-left<2){
            return v;
        }
        i=right;
        while(i>=left+2){
            vector<vector<int>>vv;
            vv=twosum(nums,target-nums[i],left,i-1);
            for(j=0;j<vv.size();j++){
                vv[j].push_back(nums[i]);
                v.push_back(vv[j]);
            }
            while(i>=left+2&&nums[i-1]==nums[i]){
                i--;
            }
            i--;
        }
        return v;
    }
    vector<vector<int>> fourSum(vector<int>& nums, int target) {
        sort(nums.begin(),nums.end());
        vector<vector<int>>res;
        int size=nums.size();
        int i,j,k;
        if(size<4){
            return res;
        }
        i=size-1;
        while(i>2){
            vector<vector<int>>v;
            v=threesum(nums,target-nums[i],0,i-1);
            for (j=0;j<v.size();j++){
                v[j].push_back(nums[i]);
                res.push_back(v[j]);
            }
            while(i>2&&nums[i]== nums[i-1]){
                i--;
            }
            i--;
        }
        return res;
    }
};

思路二：先遍历两个数，求和，然后转化为剩下元素的2SUM问题。

/* 注意：调用这个函数之前一定要先给 nums 排序 */
vector<vector<int>> nSumTarget(
    vector<int>& nums, int n, int start, int target) {

    int sz = nums.size();
    vector<vector<int>> res;
    // 至少是 2Sum，且数组大小不应该小于 n
    if (n < 2 || sz < n) return res;
    // 2Sum 是 base case
    if (n == 2) {
        // 双指针那一套操作
        int lo = start, hi = sz - 1;
        while (lo < hi) {
            int sum = nums[lo] + nums[hi];
            int left = nums[lo], right = nums[hi];
            if (sum < target) {
                while (lo < hi && nums[lo] == left) lo++;
            } else if (sum > target) {
                while (lo < hi && nums[hi] == right) hi--;
            } else {
                res.push_back({left, right});
                while (lo < hi && nums[lo] == left) lo++;
                while (lo < hi && nums[hi] == right) hi--;
            }
        }
    } else {
        // n > 2 时，递归计算 (n-1)Sum 的结果
        for (int i = start; i < sz; i++) {
            vector<vector<int>> 
                sub = nSumTarget(nums, n - 1, i + 1, target - nums[i]);
            for (vector<int>& arr : sub) {
                // (n-1)Sum 加上 nums[i] 就是 nSum
                arr.push_back(nums[i]);
                res.push_back(arr);
            }
            while (i < sz - 1 && nums[i] == nums[i + 1]) i++;
        }
    }
    return res;
}

多数组Sum

数组列表 A , B , C , D ,计算有多少个元组 (i, j, k, l) ，使得 A[i] + B[j] + C[k] + D[l] = 0

class Solution {
public:
    int fourSumCount(vector<int>& A, vector<int>& B, vector<int>& C, vector<int>& D,int target) {
        sort(A.begin(), A.end());
        sort(B.begin(), B.end());
        sort(C.begin(), C.end());
        sort(D.begin(), D.end());
        int i,counts=0;
        for(i=0;i<A.size();i++){
            counts+=threesumcount(B, C, D,target-A[i]);
        }
        return counts;
    }
    int threesumcount(vector<int>& A, vector<int>& B,vector<int>& C,int target){
        int counts=0;
        int i;
        for(i = 0; i < A.size();i++){
            counts+=twosumcount(C,B,target-A[i]);
        }
        return counts;
    }
    int twosumcount(vector<int>& A, vector<int>& B,int result){
        int left =0;
        int right=B.size();
        int i,j;
        int counts=0;
        while(left<A.size() && right>-1){
            if(A[left]+B[right]>result){
                left++;
            }else if(A[left]+B[right]<result){
                right--;
            }
            else{
                counts++;
                left++;
            }
        }
        return counts;
    }
};

上面的代码本地没问题提交竟然报了错....下面是用hashmap的方法解的，无需排序更快。

class Solution {
public:
    int fourSumCount(vector<int>& A, vector<int>& B, vector<int>& C, vector<int>& D) {
        unordered_map<int,int>m;
        int i,j;
        int result = 0;
        for(i=0;i<A.size();i++){
            for(j=0;j<B.size();j++){
                if(m.count(A[i]+B[j])==0){
                    m[(A[i]+B[j])]=1;
                }else{
                    m[(A[i]+B[j])]++;
                }
            }
        }
        int counts=0;
        for(i=0;i<C.size();i++){
            for(j=0;j<D.size();j++){
                if(m.count(result-(C[i]+D[j]))){
                    counts+=m[result-(C[i]+D[j])];
                }
            }
        }
        return counts;
    }
};

Two sum及其衍生问题

猜你喜欢

热点阅读