18/454-四数之和

LeetCode 18. 4Sum

LeetCode-18

Given an array nums of n integers, return an array of all the unique quadruplets [nums[a], nums[b], nums[c], nums[d]] such that:

• 0 <= a, b, c, d < n
• a, b, c, and d are distinct.
• nums[a] + nums[b] + nums[c] + nums[d] == target

You may return the answer in any order.

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]]

method: 双指针

在三数之和的基础上再套一层循环，变成四个指针i, j, l, r

vector<vector<int>> fourSum(vector<int>& nums, int target) {
    vector<vector<int>> ret;
    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) {     // 会溢出，把加移过去变成减
                if (nums[i] + nums[j] < target - nums[l] - nums[r]) l++;
                else if (nums[i] + nums[j] > target - nums[l] - nums[r]) r--;
                else {
                    ret.push_back(vector<int>{nums[i],nums[j],nums[l],nums[r]});
                    while (l < r && nums[l] == nums[l + 1]) l++;
                    while (l < r && nums[r] == nums[r - 1]) r--;
                    l++;
                    r--;
                }
            }
        }
    }
    return ret;
}

---

LeetCode 454. 4Sum II

LeetCode-454

Given four integer arrays nums1, nums2, nums3, and nums4 all of length n, return the number of tuples (i, j, k, l) such that:

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
Explanation:
The two tuples are:
1. 1 + (-2) + (-1) + 2 = 0
2. 2 + (-1) + (-1) + 0 = 0

method: 哈希表

题意：从4个数组里各取一个数，加起来为0，不用去重
用哈希表存A和B之和的结果及其出现次数，看C和D之和有没有其相反数

int fourSumCount(vector<int>& A, vector<int>& B, vector<int>& C, vector<int>& D) {
    unordered_map<int, int> hash;
    for (auto a : A) {
        for (auto b : B) {
            hash[a + b]++;  // A+B和的可能
        }
    }
    int cnt = 0;
    for (auto c : C) {
        for (auto d : D) {
            cnt += hash[-(c + d)];  // C+D和的可能，互为相反数就可以
        }    
    }
    return cnt;
}