題目描述

給你四個整數數組 nums1、nums2、nums3 和 nums4 ，數組長度都是 n ，請你計算有多少個元組 (i, j, k, l) 能滿足：
0 <= i, j, k, l < n
nums1[i] + nums2[j] + nums3[k] + nums4[l] == 0示例 1：
輸入：nums1 = [1,2], nums2 = [-2,-1], nums3 = [-1,2], nums4 = [0,2]
輸出：2
解釋：
兩個元組如下：
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
3. 
示例 2：
輸入：nums1 = [0], nums2 = [0], nums3 = [0], nums4 = [0]
輸出：1

思想

1. 遍歷 nums1 和 nums2：
   雙重循環遍歷 nums1 和 nums2 的每個元素 i 和 j。計算和 i+j，并將該和作為鍵存儲到 map 中，值為這個和出現的次數（如果已存在，則增加計數）。
2. 遍歷 nums3 和 nums4：
   再次使用雙重循環，這次遍歷 nums3 和 nums4 的每個元素 k 和 q。
   計算 - (k + q)，即我們需要在 map 中找到的目標值，使得四個數之和為零。
   使用 map.find(target) 查找是否有符合條件的鍵值對存在。如果找到了，將找到的值（即前面計算出的和的出現次數）加到 count 中。

舉例說明：

第一步：計算 nums1 和 nums2 的所有可能的元素和
循環過程：
對于 nums1[0] = 1：nums2[0] = -2 -> 和為 -1，map[-1] = 1nums2[1] = -1 -> 和為 0，map[0] = 1
對于 nums1[1] = 2：nums2[0] = -2 -> 和為 0，map[0] 現在增加為 2（因為已經有一個和為 0）nums2[1] = -1 -> 和為 1，map[1] = 1
此時，map 的內容如下：-1 出現 1 次0 出現 2 次1 出現 1 次第二步：計算 nums3 和 nums4 的所有可能的元素和的相反數，并查找是否存在于 map 中
循環過程：
對于 nums3[0] = -1：nums4[0] = 0 -> 和為 -1，相反數是 1，map 中 1 出現了 1 次，所以 count += 1nums4[1] = 2 -> 和為 1，相反數是 -1，map 中 -1 出現了 1 次，所以 count += 1
對于 nums3[1] = 2：nums4[0] = 0 -> 和為 2，相反數是 -2，map 中不存在 -2nums4[1] = 2 -> 和為 4，相反數是 -4，map 中不存在 -4
結果：count 的值為 2，這表示有兩個元組滿足條件：(0, 0, 0, 1) -> nums1[0] + nums2[0] + nums3[0] + nums4[1] = 1 + (-2) + (-1) + 2 = 0(1, 1, 0, 0) -> nums1[1] + nums2[1] + nums3[0] + nums4[0] = 2 + (-1) + (-1) + 0 = 0

完整代碼

#include<iostream>
#include<vector>
#include<unordered_map>
using namespace std;class Solution {
public:int fourSumCount(vector<int>& nums1, vector<int>& nums2, vector<int>& nums3, vector<int>& nums4) {unordered_map<int, int> map;int count = 0;for(int i : nums1){for(int j : nums2){map[i + j]++;}}for(int k : nums3){for(int q : nums4){int target = 0 - (k + q);if(map.find(target) != map.end()){count += map[target];}}}return count;}
};int main()
{Solution s;vector<int> nums1 = {1,2};vector<int> nums2 = {-2,-1};vector<int> nums3 = {-1,2};vector<int> nums4 = {0,2};cout << s.fourSumCount(nums1, nums2, nums3, nums4) << endl;return 0;
}