k number sum problem

Title: given n integers, k and target, find k numbers in these n numbers, make the sum of k numbers equal to target, and output all possible solutions.

Solution: if k is an even number, sort n integers first, and then find the sum of each k/2 number (for example, find the sum of each two numbers in the 4sum problem) in the HashMap (the set of array subscripts of key: two numbers and value: sum). Traverse the HashMap. If target-x exists for the current element X and is also in the HashMap, pair the subscripts set corresponding to X and target-x to produce A solution needs to be de duplicated in the process (at present, we only want to sort the paired array containing k subscripts, and then use set to de duplicate).

If K is an odd number, sort n integers first, and then find the sum of every k/2 numbers and store it in HashMap. Traverse the array. If there is a pair of X and target-a-x in the current element a and HashMap, pair the subscript set corresponding to X and target-a-x to generate a solution, which needs to be de duplicated in the process.

class Solution {
public:
    void mergeTwoSum(vector<int>& nums, set<vector<int>>& res, vector<vector<int>> list1, vector<vector<int>> list2) {
        for (int i = 0; i < list1.size(); i++)
        {
            for (int j = 0; j < list2.size(); j++)
            {
                if (list1[i][0] == list2[j][0] || list1[i][1] == list2[j][0])
                    continue;
                if (list1[i][0] == list2[j][1] || list1[i][1] == list2[j][1])
                    continue;
                vector<int> temp;
                temp.push_back(nums[list1[i][0]]);
                temp.push_back(nums[list1[i][1]]);
                temp.push_back(nums[list2[j][0]]);
                temp.push_back(nums[list2[j][1]]);
                sort(temp.begin(), temp.end());
                res.insert(temp);
            }
        }
    }
    
    vector<vector<int>> fourSum(vector<int>& nums, int target) {
        int n = nums.size();
        vector<vector<int>> res;
        set<vector<int>> res_set;
        map<int, vector<vector<int>>> twoSum;
        sort(nums.begin(), nums.end());
        for (int i = 0; i < n; i++)
        {
            for (int j = i + 1; j < n; j++)
            {
                vector<int> temp;
                temp.push_back(i);
                temp.push_back(j);
                twoSum[nums[i] + nums[j]].push_back(temp);
            }
        }
        map<int, vector<vector<int>>>::iterator it;
        for (it = twoSum.begin(); it != twoSum.end(); it++)
        {
            int a = it->first;
            int b = target - a;
            if (a > b)
                break;
            if (twoSum.find(b) != twoSum.end())
                mergeTwoSum(nums, res_set, it->second, twoSum[b]);
        }
        res.assign(res_set.begin(), res_set.end());
        return res;
    }
};

Tags: Erlang

Posted on Sat, 02 Nov 2019 04:33:32 -0700 by hijack