22LeetCode link: [ 454. 4Sum II] ( https://leetcode.com/problems/problem ) , difficulty: ** Medium** .
33
44## LeetCode description of "454. 4Sum II"
5- Given four integer arrays ` nums1 ` , ` nums2 ` , ` nums3 ` , and ` nums4 ` all of length ` n ` , return the number of tuples` (i, j, k, l)` such that:
5+ Given four integer arrays ` nums1 ` , ` nums2 ` , ` nums3 ` , and ` nums4 ` all of length ` n ` , return the number of tuples ` (i, j, k, l) ` such that:
66
7- * ` 0 <= i, j, k, l < n `
8- * ` nums1[i] + nums2[j] + nums3[k] + nums4[l] == 0 `
7+ - ` 0 <= i, j, k, l < n `
8+ - ` nums1[i] + nums2[j] + nums3[k] + nums4[l] == 0 `
99
1010### [ Example 1]
1111** Input** : ` nums1 = [1,2], nums2 = [-2,-1], nums3 = [-1,2], nums4 = [0,2] `
@@ -30,33 +30,36 @@ The two tuples are:
3030- ` n == nums3.length `
3131- ` n == nums4.length `
3232- ` 1 <= n <= 200 `
33- - ` -2** 28 <= nums1[i], nums2[i], nums3[i], nums4[i] <= 2** 28 `
33+ - ` -2^ 28 <= nums1[i], nums2[i], nums3[i], nums4[i] <= 2^ 28 `
3434
3535## Intuition
36361 . Because the final requirement is to take one number from each group of numbers, the four groups of numbers can be split into ** two groups of two** .
37372 . Count the number of each ` sum ` . Use ` Map ` to store, ` key ` is ` sum ` , ` value ` is ` count ` .
38383 . Iterate over ` nums3 ` and ` nums4 ` , if ` -(num3 + num4) ` exists in ` keys ` of ` Map ` , then ` count ` is included in the total.
3939
4040## Steps
41+
41421 . Count the number of each ` sum ` . Use ` Map ` to store, ` key ` is ` sum ` , ` value ` is ` count ` .
42- ``` python
43- num_to_count = defaultdict(int )
4443
45- for num1 in nums1:
46- for num2 in nums2:
47- num_to_count[num1 + num2] += 1
48- ```
44+ ```python
45+ num_to_count = defaultdict(int)
46+
47+ for num1 in nums1:
48+ for num2 in nums2:
49+ num_to_count[num1 + num2] += 1
50+ ```
4951
50522 . Iterate over ` nums3 ` and ` nums4 ` , if ` -(num3 + num4) ` exists in ` keys ` of ` Map ` , then ` count ` is included in the total.
51- ``` python
52- result = 0
53-
54- for num3 in nums3:
55- for num4 in nums4:
56- result += num_to_count[- (num3 + num4)]
5753
58- return result
59- ```
54+ ```python
55+ result = 0
56+
57+ for num3 in nums3:
58+ for num4 in nums4:
59+ result += num_to_count[-(num3 + num4)]
60+
61+ return result
62+ ```
6063
6164## Complexity
6265* Time: ` O(n * n) ` .
0 commit comments