LC-454

题目

给你四个整数数组 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
解释：
两个元组如下：

1. (0, 0, 0, 1) -> nums1[0] + nums2[0] + nums3[0] + nums4[1] = 1 + (-2) + (-1) + 2 = 0
2. (1, 1, 0, 0) -> nums1[1] + nums2[1] + nums3[0] + nums4[0] = 2 + (-1) + (-1) + 0 = 0

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/4sum-ii
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

Java实现（双for + HashMap）

package LC.hash;

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

public class LC454 {
    public static void main(String[] args) {
        int[] nums1 = {1, 2};
        int[] nums2 = {-2, -1};
        int[] nums3 = {-1, 2};
        int[] nums4 = {0, 2};
        System.out.println(fourSumCount(nums1, nums2, nums3, nums4));
    }

    public static int fourSumCount(int[] A, int[] B, int[] C, int[] D) {
        Map<Integer, Integer> map = new HashMap<>();
        int res = 0;
        for (int i = 0; i < A.length; i++) {
            for (int j = 0; j < B.length; j++) {
                int sumAB = A[i] + B[j];
                if (map.containsKey(sumAB))
                    map.put(sumAB, map.get(sumAB) + 1);
                else map.put(sumAB, 1);
            }
        }

        for (int i = 0; i < C.length; i++) {
            for (int j = 0; j < D.length; j++) {
                int sumCD = -(C[i] + D[j]);
                if (map.containsKey(sumCD))
                    res += map.get(sumCD);
            }
        }
        return res;
    }
}

Python实现

class Solution:
    def fourSumCount(self, A: List[int], B: List[int], C: List[int], D: List[int]) -> int:
        countAB = collections.Counter(u + v for u in A for v in B)
        ans = 0
        for u in C:
            for v in D:
                if -u -v in countAB:
                    ans = ans + countAB[-u -v]
        return ans

总结

看到形如：A+B....+N = 0 的式子，

要转换为(A+...T)=-((T+1)...+N)再计算，这个T的分割点一般是一半，特殊情况下需要自行判断。

定T是解题的关键。

import java.util.HashMap;

class Solution {
    private static class Node {
        int value;
        int count;
        Node next;

        public Node(int value) {
            this.value = value;
            this.count = 1;
        }

        public Node(int value, Node next) {
            this.value = value;
            this.count = 1;
            this.next = next;
        }
    }

    private static class Map {

        Node[] table;

        public Map(int initalCapacity) {
            if (initalCapacity < 16) {
                initalCapacity = 16;
            } else {
                initalCapacity = Integer.highestOneBit(initalCapacity - 1) << 1;
            }
            table = new Node[initalCapacity];
        }

        // 拷贝的HashMap的hash方法
        private int hash(int value) {
            if (value < 0) {
                value = -value;
            }
            int h;
            return (value == 0) ? 0 : (h = value) ^ (h >>> 16);
        }

        public void put(int value) {
            int tableIndex = hash(value) & table.length - 1;
            Node head = table[tableIndex];
            if (head == null) {
                table[tableIndex] = new Node(value);
                return;
            }
            Node cur = head;
            while (cur != null) {
                if (cur.value == value) {
                    cur.count++;
                    return;
                }
                cur = cur.next;
            }

            // 头插法
            table[tableIndex] = new Node(value, head);
        }

        public int getCount(int value) {
            int tableIndex = hash(value) & table.length - 1;
            Node head = table[tableIndex];
            if (head == null) {
                return 0;
            }
            Node cur = head;
            while (cur != null) {
                if (cur.value == value) {
                    return cur.count;
                }
                cur = cur.next;
            }
            return 0;
        }
    }

    public int fourSumCount(int[] A, int[] B, int[] C, int[] D) {

        // 避免扩容, 初始化一个最大初始容量
        Map abMap = new Map(A.length * B.length);

        for (int a : A) {
            for (int b : B) {
                abMap.put(a + b);
            }
        }

        int res = 0;
        for (int c : C) {
            for (int d : D) {
                res += abMap.getCount(-c - d);
            }
        }
        return res;
    }

}