18. 4Sum

作者: Nautilus1 | 来源:发表于2017-10-24 10:34 被阅读0次

    题目描述:给定一个有n个整数的数组S和目标值target,找到其中所有由四个数a、b、c、d组成,使得a + b + c + d = target 的四元组。如:

    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 的思路一样,先排序再左右夹逼,由于多一层循环复杂度O(n^3)。或者用 hashmap 先缓存两个数的和,这也可用于3sum, 最终复杂度O(n^3)。

    方法一:先排序再左右夹逼,时间复杂度O(n^3),空间O(1)。

    class Solution {
    public:
        vector<vector<int>> fourSum(vector<int>& nums, int target) {
            vector< vector<int> > ans;
            if (nums.size() < 4) return ans;
            
            sort(nums.begin(), nums.end());
            for (int i = 0; i < nums.size() - 3; i ++)
            {
                for (int j = i + 1; j < nums.size() - 2; j ++)
                {
                    int l = j + 1, r = nums.size() - 1;
                    while(l < r)
                    {
                        if (nums[i] + nums[j] + nums[l] + nums[r] < target)
                            l ++;
                        else if (nums[i] + nums[j] + nums[l] + nums[r] > target)
                            r --;
                        else
                        {
                            ans.push_back({nums[i], nums[j], nums[l], nums[r]});
                            l ++;
                            r --;
                        }
                    }
                }
            }
            sort(ans.begin(), ans.end());
            ans.erase(unique(ans.begin(), ans.end()), ans.end());          //erase函数删除两迭代器之间的元素,unique返回的是重排后第一个多余元素的位置
            return ans;
        }
    };
    

    方法二:先用 hashmap 缓存两个数的和,平均O(n^2 ),最坏O(n^4 ),空间复杂度O(n^2)。

    class Solution {
    public:
        vector<vector<int>> fourSum(vector<int>& nums, int target) {
            vector< vector<int> > ans;
            if (nums.size() < 4) return ans;
            
            sort(nums.begin(), nums.end());
            unordered_map<int, vector<pair<int, int> > > mp;           //两数和为键,这两数下标对为值
            for (int i = 0; i < nums.size(); i ++)
                for (int j = i + 1; j < nums.size(); j ++)
                    mp[nums[i] + nums[j]].push_back(pair<int, int>(i, j));
            
            for (int i = 0; i < nums.size(); i ++)
            {
                for (int j = i + 1; j < nums.size(); j ++)
                {
                    int gap = target - nums[i] - nums[j];
                    if (mp.find(gap) == mp.end())
                        continue;
                    
                    auto vec = mp[gap];
                    for (int k = 0; k < vec.size(); k++)
                    {
                        if (i <= vec[k].second)       //有重叠,因为存入map时pair中小下标在前,大下标在后。i < j, vec[k].first < vec[k].second。改为 (j >= vec[k].first) 也可通过。保证a != c && a != d && b != c && b != d
                            continue;
                        
                        ans.push_back({nums[ vec[k].first ], nums[ vec[k].second ], nums[i], nums[j]});             //a≤b≤c≤d
                    }
                }
            }
            sort(ans.begin(), ans.end());     
            ans.erase(unique(ans.begin(), ans.end()), ans.end());          //去重,不能包含重复的四元组
            return ans;
        }
    };
    

    相关文章

      网友评论

        本文标题:18. 4Sum

        本文链接:https://www.haomeiwen.com/subject/axqtpxtx.html