LeetCode: 454. 4Sum II

友情支持

如果您觉得这个笔记对您有所帮助，看在D瓜哥码这么多字的辛苦上，请友情支持一下，D瓜哥感激不尽，😜

支付宝

有些打赏的朋友希望可以加个好友，欢迎关注D 瓜哥的微信公众号，这样就可以通过公众号的回复直接给我发信息。

wx jikerizhi

公众号的微信号是: jikerizhi。因为众所周知的原因，有时图片加载不出来。如果图片加载不出来可以直接通过搜索微信号来查找我的公众号。

454. 4Sum II

LeetCode - 4Sum II

原想是三层循环，就是 O(N³) 的复杂度。降低为两层循环，把时间复杂度也减低一级。

Given four lists A, B, C, D of integer values, compute how many tuples (i, j, k, l) there are such that A[i] + B[j] + C[k] + D[l] is zero.

To make problem a bit easier, all A, B, C, D have same length of N where 0 ≤ N ≤ 500. All integers are in the range of -2²⁸ to 2²⁸ - 1 and the result is guaranteed to be at most 2³¹ - 1.

Example:

Input:
A = [ 1, 2]
B = [-2,-1]
C = [-1, 2]
D = [ 0, 2]

Output:
2

Explanation:
The two tuples are:
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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
/**
 * Runtime: 94 ms, faster than 38.81% of Java online submissions for 4Sum II.
 *
 * Memory Usage: 58.6 MB, less than 64.00% of Java online submissions for 4Sum II.
 *
 * https://leetcode.com/problems/4sum-ii/discuss/93920/Clean-java-solution-O(n2)[Clean java solution O(n^2) - LeetCode Discuss]
 */
public int fourSumCount(int[] A, int[] B, int[] C, int[] D) {
    Map<Integer, Integer> numToCountMap = new HashMap<>();
    for (int i = 0; i < A.length; i++) {
        for (int j = 0; j < B.length; j++) {
            int value = A[i] + B[j];
            Integer count = numToCountMap.getOrDefault(value, 0);
            numToCountMap.put(value, ++count);
        }
    }
    int result = 0;
    for (int i = 0; i < C.length; i++) {
        for (int j = 0; j < D.length; j++) {
            result += numToCountMap.getOrDefault(0 - C[i] - D[j], 0);
        }
    }
    return result;
}