第454題.四數相加II

力扣題目鏈接(opens new window)

給定四個包含整數的數組列表?A , B , C , D ,計算有多少個元組 (i, j, k, l)?，使得?A[i] + B[j] + C[k] + D[l] = 0。

為了使問題簡單化，所有的 A, B, C, D 具有相同的長度?N，且 0 ≤ N ≤ 500 。所有整數的范圍在 -2^28 到 2^28 - 1 之間，最終結果不會超過?2^31 - 1 。

例如1:

輸入:

• A = [ 1, 2]
• B = [-2,-1]
• C = [-1, 2]
• D = [ 0, 2]

輸出:

2

解釋:

兩個元組如下:

1. (0, 0, 0, 1) -> A[0] + B[0] + C[0] + D[1] = 1 + (-2) + (-1) + 2 = 0
2. (1, 1, 0, 0) -> A[1] + B[1] + C[0] + D[0] = 2 + (-1) + (-1) + 0 = 0

示例 2：

輸入：nums1 = [0], nums2 = [0], nums3 = [0], nums4 = [0]
輸出：1

??提示：

• n == nums1.length
• n == nums2.length
• n == nums3.length
• n == nums4.length
• 1 <= n <= 200
• -228 <= nums1[i], nums2[i], nums3[i], nums4[i] <= 228

思路

本題乍眼一看好像和0015.三數之和?(opens new window)，0018.四數之和?(opens new window)差不多，其實差很多。

本題是使用哈希法的經典題目，而0015.三數之和?(opens new window)，0018.四數之和?(opens new window)并不合適使用哈希法，因為三數之和和四數之和這兩道題目使用哈希法在不超時的情況下做到對結果去重是很困難的，很有多細節需要處理。

而這道題目是四個獨立的數組，只要找到A[i] + B[j] + C[k] + D[l] = 0就可以，不用考慮有重復的四個元素相加等于0的情況，所以相對于題目18. 四數之和，題目15.三數之和，還是簡單了不少！

如果本題想難度升級：就是給出一個數組（而不是四個數組），在這里找出四個元素相加等于0，答案中不可以包含重復的四元組，大家可以思考一下，后續的文章我也會講到的。

本題解題步驟：

1. 首先定義 一個unordered_map，key放a和b兩數之和，value 放a和b兩數之和出現的次數。
2. 遍歷大A和大B數組，統計兩個數組元素之和，和出現的次數，放到map中。
3. 定義int變量count，用來統計 a+b+c+d = 0 出現的次數。
4. 再遍歷大C和大D數組，找到如果 0-(c+d) 在map中出現過的話，就用count把map中key對應的value也就是出現次數統計出來。這里其實就是在找可以讓nums3和nums4相加為0的相反數，這也是為什么是減號！
5. 最后返回統計值 count 就可以了

class Solution {// 方法：計算四個數組中滿足和為0的元組數量public int fourSumCount(int[] nums1, int[] nums2, int[] nums3, int[] nums4) {int res = 0; // 初始化結果計數器// 創建哈希表存儲前兩個數組元素兩兩相加的和及其出現次數Map<Integer, Integer> map = new HashMap<Integer, Integer>();// 遍歷nums1和nums2，計算所有兩數之和for (int i : nums1) {          // 遍歷第一個數組for (int j : nums2) {      // 遍歷第二個數組int sum = i + j;       // 計算兩數之和// 將和存入map：若存在則計數+1，不存在則初始化為1map.put(sum, map.getOrDefault(sum, 0) + 1);}}// 遍歷nums3和nums4，查找互補和for (int i : nums3) {          // 遍歷第三個數組for (int j : nums4) {      // 遍歷第四個數組int complement = 0 - i - j; // 計算需要的互補值（使四數和為0）// 累加哈希表中互補值出現的次數（若不存在則加0）res += map.getOrDefault(complement, 0);}}return res; // 返回滿足條件的元組總數}
}