四數(shù)相加（Hash）
2022-09-06 22:39:36

一、題目鏈接

? ? ? ? ? ? ???四數(shù)相加??

二、題目描述

給你四個(gè)整數(shù)數(shù)組 nums1、nums2、nums3 和 nums4 ，數(shù)組長度都是 n ，請你計(jì)算有多少個(gè)元組 (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 解釋： 兩個(gè)元組如下：

(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)來進(jìn)行查找并統(tǒng)計(jì)解結(jié)果

? 缺點(diǎn)：時(shí)間復(fù)雜度較高

方法二：集合法

?通過使用集合Map

鍵：存儲元素的值

值：存儲元素出現(xiàn)的次數(shù)

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

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

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

四、核心代碼實(shí)現(xiàn)

class Solution {
    public int fourSumCount(int[] nums1, int[] nums2, int[] nums3, int[] nums4) {
        //map存儲鍵值對，<元素，元素對應(yīng)出現(xiàn)的次數(shù)>
        Map<Integer,Integer> map=new HashMap<>();
        int total=0;
        int temp;
        //遍歷數(shù)組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的元素和的補(bǔ)集的負(fù)數(shù)是否存在map中，如果存在統(tǒng)計(jì)次數(shù)
        for(int i:nums3){
            for(int j:nums4){
                temp=i+j;
                if(map.containsKey(0-temp)){
                    total+=map.get(0-temp);//由于map中存儲的次數(shù)是不同的情況，所以均加上（滿足條件）
                }
            }
        }
        return total;
    }
}