Hash table - sum of arrays

1. Sum of two numbers
   Given an array of integers nums And an integer target value target, Please find... In the array And is the target value target the Two Integers , And return their array subscripts .

You can assume that each input corresponds to only one answer . however , The same element in the array cannot be repeated in the answer .

You can return the answers in any order .

Example 1：

Input ：nums = [2,7,11,15], target = 9
Output ：[0,1]
explain ： because nums[0] + nums[1] == 9 , return [0, 1] .
Example 2：

Input ：nums = [3,2,4], target = 6
Output ：[1,2]
Example 3：

Input ：nums = [3,3], target = 6
Output ：[0,1]

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        unordered_map<int, int> map;
        for(int i = 0; i < nums.size(); ++i){
            if(map.find(target - nums[i]) != map.end()){
                return vector<int>{i, map[target - nums[i]]};
            } else {
                map[nums[i]] = i;
            }
        }
        return vector<int>{};
    }
};a

454. Add four numbers II
     Here are four integer arrays nums1、nums2、nums3 and nums4 , The length of the array is n , Please calculate how many tuples there are (i, j, k, l) To meet the ：

0 <= i, j, k, l < n
nums1[i] + nums2[j] + nums3[k] + nums4[l] == 0

Example 1：

Input ：nums1 = [1,2], nums2 = [-2,-1], nums3 = [-1,2], nums4 = [0,2]
Output ：2
explain ：
Two tuples are as follows ：

1. (0, 0, 0, 1) -> nums1[0] + nums2[0] + nums3[0] + nums4[1] = 1 + (-2) + (-1) + 2 = 0
2. (1, 1, 0, 0) -> nums1[1] + nums2[1] + nums3[0] + nums4[0] = 2 + (-1) + (-1) + 0 = 0
   Example 2：

Input ：nums1 = [0], nums2 = [0], nums3 = [0], nums4 = [0]
Output ：1

class Solution {
public:
    int fourSumCount(vector<int>& nums1, vector<int>& nums2, vector<int>& nums3, vector<int>& nums4) {
        unordered_map<int, int> map;
        for(auto a : nums1){
            for(auto b : nums2){
                map[a + b]++;
            }
        }
        int cnt = 0;
        for(auto c : nums3){
            for(auto d : nums4){
                if(map.find(0 - (c + d)) != map.end()){
                    cnt += map[0 - (c + d)];
                }
            }
        }
        return cnt;
    }
};

383. Ransom letter
     Here are two strings ：ransomNote and magazine , Judge ransomNote Can it be done by magazine The characters inside make up .

If possible , return true ; Otherwise return to false .

magazine Each character in can only be in ransomNote Used once in .

Example 1：

Input ：ransomNote = “a”, magazine = “b”
Output ：false
Example 2：

Input ：ransomNote = “aa”, magazine = “ab”
Output ：false
Example 3：

Input ：ransomNote = “aa”, magazine = “aab”
Output ：true

class Solution {
public:
    bool canConstruct(string ransomNote, string magazine) {
        unordered_map<int, int> mag;
        for(int i = 0; i < magazine.size(); ++i){
            mag[magazine[i]]++;
        }
        for(int i = 0; i < ransomNote.size(); ++i){
            if(mag.find(ransomNote[i]) != mag.end()){
                mag[ransomNote[i]]--;
            } else {
                return false;
            }
            if(mag[ransomNote[i]] == 0){
                mag.erase(ransomNote[i]);
            }
        }
        return true;
    }
};

15. Sum of three numbers
    Give you one containing n Array of integers nums, Judge nums Are there three elements in a,b,c , bring a + b + c = 0 ？ Please find out all and for 0 Triple without repetition .

Be careful ： Answer cannot contain duplicate triples .

Example 1：

Input ：nums = [-1,0,1,2,-1,-4]
Output ：[[-1,-1,2],[-1,0,1]]
Example 2：

Input ：nums = []
Output ：[]
Example 3：

Input ：nums = [0]
Output ：[]

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

18. Sum of four numbers
    Here you are n An array of integers nums , And a target value target . Please find and return the quads that meet all the following conditions and are not repeated [nums[a], nums[b], nums[c], nums[d]] （ If two Quad elements correspond to each other , It is considered that two quads repeat ）：

0 <= a, b, c, d < n
a、b、c and d Different from each other
nums[a] + nums[b] + nums[c] + nums[d] == target
You can press In any order Return to the answer .

Example 1：

Input ：nums = [1,0,-1,0,-2,2], target = 0
Output ：[[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]
Example 2：

Input ：nums = [2,2,2,2,2], target = 8
Output ：[[2,2,2,2]]

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