2
2
LeetCode link: [ 454. 4Sum II] ( https://leetcode.com/problems/problem ) , difficulty: ** Medium** .
3
3
4
4
## 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:
6
6
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 `
9
9
10
10
### [ Example 1]
11
11
** Input** : ` nums1 = [1,2], nums2 = [-2,-1], nums3 = [-1,2], nums4 = [0,2] `
@@ -30,33 +30,36 @@ The two tuples are:
30
30
- ` n == nums3.length `
31
31
- ` n == nums4.length `
32
32
- ` 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 `
34
34
35
35
## Intuition
36
36
1 . 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** .
37
37
2 . Count the number of each ` sum ` . Use ` Map ` to store, ` key ` is ` sum ` , ` value ` is ` count ` .
38
38
3 . Iterate over ` nums3 ` and ` nums4 ` , if ` -(num3 + num4) ` exists in ` keys ` of ` Map ` , then ` count ` is included in the total.
39
39
40
40
## Steps
41
+
41
42
1 . Count the number of each ` sum ` . Use ` Map ` to store, ` key ` is ` sum ` , ` value ` is ` count ` .
42
- ``` python
43
- num_to_count = defaultdict(int )
44
43
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
+ ```
49
51
50
52
2 . 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)]
57
53
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
+ ```
60
63
61
64
## Complexity
62
65
* Time: ` O(n * n) ` .
0 commit comments