454. Sum of four numbers (hash table)

subject ：

Given a list of four arrays containing integers  A , B , C , D , Calculate how many tuples there are (i, j, k, l) , bring  A[i] + B[j] + C[k] + D[l] = 0.

To simplify the problem , be-all A, B, C, D Same length  N, And 0 ≤ N ≤ 500 . All integers are in the range of -2^28 To 2^28 - 1 Between , The final result will not exceed  2^31 - 1.

Method ： Hash table method

Ideas ： Group four arrays in pairs , Record the sum of two arrays and their   Number of occurrences of and , And take the value of sum as key, The number of occurrences is value Stored in hash table ,

The values of the other two arrays and are used as key To find out if the hash table exists key Make the sum of the four arrays 0, namely map.containKey（0-nums3[i]+nums4[j]）

If you find a qualified key value , On the number of updates , After traversal, return the last occurrence number

import java.util.HashMap;
import java.util.Map;

public class Sishuzhihe2 {
    // So let's define a hashmap,key Deposit a and b Sum of two numbers ,value discharge a and b The number of times the sum of two numbers appears 
    // Traverse A,B Two arrays , The number of occurrences of the sum of statistics array elements , And put in map
    // Definition int Variable count, Statistics a+b+c+d=0 Number of occurrences 
    // In a traverse C and D Array , If you find 0-（c+d） stay map If you've seen it in the past , Just use count hold map in key Corresponding value That is, the number of occurrences 
    // return count
    public int fourSumCount(int [] nums1,int[] nums2,int[] nums3,int[] nums4){
        Map<Integer,Integer> map = new HashMap<>();
        int temp;
        int res = 0;
        // Count the sum of the elements in two arrays , At the same time, count the number of occurrences , Put in map
        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);
                }
            }
        }

        // Count the elements and... Of the remaining two arrays , stay map Found in key bring , Add to 0, Record the number of occurrences at the same time 
        for (int i : nums3) {
            for (int j : nums4) {
                temp= i+j;
                if (map.containsKey(0-temp)){
                    res+= map.get(0-temp);
                }
            }
        }
        return res;
    }

    public static void main(String[] args) {
        int [] a = {1,2};
        int [] b = {-2,-1};
        int [] c = {-1,2};
        int [] d = {0,2};
        Sishuzhihe2 sishuzhihe2 = new Sishuzhihe2();
        int res = sishuzhihe2.fourSumCount(a,b,c,d);
        System.out.println(res);
    }
}