Leetcode question brushing: hash table 05 (adding four numbers II)

The first 454 topic . Add four numbers II

Force button topic link

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 .

for example :

Input :
A = [ 1, 2]
B = [-2,-1]
C = [-1, 2]
D = [ 0, 2]
Output :
2
explain :
Two tuples are as follows :

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

Bring this question , Do you just think about the four-tier cycle like me

    /** * @param nums1 * @param nums2 * @param nums3 * @param nums4 * @return * @Version 1.0 */
    public int fourSumCount1(int[] nums1, int[] nums2, int[] nums3, int[] nums4) {
    
        int count = 0;
        for (int i = 0; i < nums1.length; i++) {
    
            for (int j = 0; j < nums1.length; j++) {
    
                for (int k = 0; k < nums1.length; k++) {
    
                    for (int l = 0; l < nums1.length; l++) {
    
                        if (nums1[i] + nums2[j] + nums3[k] + nums4[l] == 0) {
    
                            count++;
                        }
                    }
                }
            }
        }
        return count;
    }

Useless , Don't treat Li Kou like a fool , Do the questions honestly .
Think back to yesterday when you added two numbers , With hashMap, Put... Directly O(N²) Turn into O(N)
It's the same question , The first and second arrays are added separately
hold O(N⁴) Turn into O(N²)

    /** * @param nums1 * @param nums2 * @param nums3 * @param nums4 * @return * @Version 2.0 * * 1,1 0.2 -1.1 * -1 1 2 4 */
    public static int fourSumCount(int[] nums1, int[] nums2, int[] nums3, int[] nums4) {
    
        /** *  It can be similar to the sum of two numbers . hold O(N^4) Turn into O(N^2), Think with the sum of two numbers  */
        // total 
        int count = 0;
        // The length of the array 
        int n = nums1.length;
        // Result set , The key is the desired result , The value is the number of key occurrences , because set Middle key unique 
        HashMap<Integer, Integer> result = new HashMap<>();
        for (int i = 0; i < n; i++) {
    
            for (int j = 0; j < n; j++) {
    
                //set The middle key does not repeat 
                if (result.containsKey(-(nums1[i] + nums2[j]))) {
    
                    // If the key repeats , To record the number of key occurrences 
                    int value = result.get(-(nums1[i] + nums2[j])) + 1;
                    result.put(-(nums1[i] + nums2[j]), value);
                } else {
    
                    result.put(-(nums1[i] + nums2[j]), 1);
                }
            }
        }
        for (int i = 0; i < n; i++) {
    
            for (int j = 0; j < n; j++) {
    
                if (result.containsKey(nums3[i] + nums4[j])) {
    
                    // such as 1 2  The sum of appears 4 Time -1,3 4  The sum of the   Every occurrence 1 Time 1, Then add 4 Time 
                    count += result.get(nums3[i] + nums4[j]);
                }
            }
        }
        return count;
    }

Ooh, ooh, ooh ！！！
Look at the solution , Just like me , Just use the enhancement for, The speed is much faster

    /** * @param nums1 * @param nums2 * @param nums3 * @param nums4 * @return * @Version 3.0 *  enhance for Rewrite it  * */
    public static int fourSumCount3(int[] nums1, int[] nums2, int[] nums3, int[] nums4) {
    
        /** *  It can be similar to the sum of two numbers . hold O(N^4) Turn into O(N^2), Think with the sum of two numbers  */
        // total 
        int count = 0;
        // The length of the array 
        int n = nums1.length;
        // Result set , The key is the desired result , The value is the number of key occurrences , because set Middle key unique 
        HashMap<Integer, Integer> result = new HashMap<>();
        for (int i:nums1) {
    
            for (int j :nums2) {
    
                //set The middle key does not repeat 
                if (result.containsKey(-(i + j))) {
    
                    // If the key repeats , To record the number of key occurrences 
                    int value = result.get(-(i + j)) + 1;
                    result.put(-(i + j), value);
                } else {
    
                    result.put(-(i + j), 1);
                }
            }
        }
        for (int i:nums3) {
    
            for (int j :nums4) {
    
                if (result.containsKey(i + j)) {
    
                    // such as 1 2  The sum of appears 4 Time -1,3 4  The sum of the   Every occurrence 1 Time 1, Then add 4 Time 
                    count += result.get(i + j);
                }
            }
        }
        return count;
    }