四數相加（Hash）
2022-09-06 22:39:36

一、題目鏈接

? ? ? ? ? ? ???四數相加??

二、題目描述

給你四個整數數組 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 解釋： 兩個元組如下：

(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

示例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

三、題目分析

方法一：暴力遍歷法

? 通過四層循環(huán)來進行查找并統(tǒng)計解結果

? 缺點：時間復雜度較高

方法二：集合法

?通過使用集合Map

鍵：存儲元素的值

值：存儲元素出現的次數

使用兩次雙層循環(huán)來進行解決問題

第一次雙層循環(huán)遍歷存儲前兩個數組元素所有組合情況及組合值出現的次數

第二次雙層循環(huán)用來查找后兩個數組元素所有組合情況的相反數是否在集合中的鍵中存在過，如果存在，總數加該相反數出現的次數即可，反之，繼續(xù)進行循環(huán)。

四、核心代碼實現

class Solution {
    public int fourSumCount(int[] nums1, int[] nums2, int[] nums3, int[] nums4) {
        //map存儲鍵值對，<元素，元素對應出現的次數>
        Map<Integer,Integer> map=new HashMap<>();
        int total=0;
        int temp;
        //遍歷數組nums1和nums2并求出所有情況的和并記錄
        for(int i:nums1){
            for(int j:nums2){
                temp=i+j;
                if(map.containsKey(temp)){
                    map.put(temp,map.get(temp)+1);
                }else{
                    map.put(temp,1);
                }
            }
        }
        //在nums2和nums3的元素和的補集的負數是否存在map中，如果存在統(tǒng)計次數
        for(int i:nums3){
            for(int j:nums4){
                temp=i+j;
                if(map.containsKey(0-temp)){
                    total+=map.get(0-temp);//由于map中存儲的次數是不同的情況，所以均加上（滿足條件）
                }
            }
        }
        return total;
    }
}