题目

给你四个整数数组 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

来源：力扣（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;

    }

}

巴特西

LC-454

就这这个醋包了这顿饺子

最新文章

热门文章