Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly
Appearance settings

Commit d818aad

Browse filesBrowse files
BlankjBlankj
committed
add: 018
1 parent 00e6bad commit d818aad
Copy full SHA for d818aad

File tree

3 files changed

+241
-0
lines changed
Filter options

3 files changed

+241
-0
lines changed

‎README.md

Copy file name to clipboardExpand all lines: README.md
+2Lines changed: 2 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -77,6 +77,7 @@
7777
| 15 | [3Sum][015] | Array, Two Pointers |
7878
| 15 | [3Sum Closest][016] | Array, Two Pointers |
7979
| 17 | [Letter Combinations of a Phone Number][017] | String, Backtracking |
80+
| 18 | [4Sum][018] | Array, Hash Table, Two Pointers |
8081
| 19 | [Remove Nth Node From End of List][019] | Linked List, Two Pointers |
8182
| 33 | [Search in Rotated Sorted Array][033] | Arrays, Binary Search |
8283
| 43 | [Multiply Strings][043] | Math, String |
@@ -149,6 +150,7 @@
149150
[015]: https://github.com/Blankj/awesome-java-leetcode/blob/master/note/015/README.md
150151
[016]: https://github.com/Blankj/awesome-java-leetcode/blob/master/note/016/README.md
151152
[017]: https://github.com/Blankj/awesome-java-leetcode/blob/master/note/017/README.md
153+
[018]: https://github.com/Blankj/awesome-java-leetcode/blob/master/note/018/README.md
152154
[019]: https://github.com/Blankj/awesome-java-leetcode/blob/master/note/019/README.md
153155
[033]: https://github.com/Blankj/awesome-java-leetcode/blob/master/note/033/README.md
154156
[043]: https://github.com/Blankj/awesome-java-leetcode/blob/master/note/043/README.md

‎note/018/README.md

Copy file name to clipboard
+134Lines changed: 134 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,134 @@
1+
# [4Sum][title]
2+
3+
## Description
4+
5+
Given an array *S* of *n* integers, are there elements *a*, *b*, *c*, and *d* in *S* such that *a* + *b* + *c* + *d* = target? Find all unique quadruplets in the array which gives the sum of target.
6+
7+
**Note:** The solution set must not contain duplicate quadruplets.
8+
9+
```
10+
For example, given array S = [1, 0, -1, 0, -2, 2], and target = 0.
11+
12+
A solution set is:
13+
[
14+
[-1, 0, 0, 1],
15+
[-2, -1, 1, 2],
16+
[-2, 0, 0, 2]
17+
]
18+
```
19+
20+
**Tags:** Array, Hash Table, Two Pointers
21+
22+
23+
## 思路 0
24+
25+
这道题和 [3Sum][015] 的思路基本一样，先对数组进行排序，然后遍历这个排序数组，因为这次是四个元素的和，所以外层需要两重循环，然后还是用两个指针分别指向当前元素的下一个和数组尾部，判断四者的和与 `target` 的大小来移动两个指针，其中细节操作还是优化和去重。
26+
27+
```java
28+
class Solution {
29+
public List<List<Integer>> fourSum(int[] nums, int target) {
30+
List<List<Integer>> res = new ArrayList<>();
31+
int len = nums.length;
32+
if (len < 4) return res;
33+
Arrays.sort(nums);
34+
int max = nums[len - 1];
35+
if (4 * max < target) return res;
36+
for (int i = 0; i < len - 3;) {
37+
if (nums[i] * 4 > target) break;
38+
if (nums[i] + 3 * max < target) {
39+
while (nums[i] == nums[++i] && i < len - 3) ;
40+
continue;
41+
}
42+
43+
for (int j = i + 1; j < len - 2;) {
44+
int subSum = nums[i] + nums[j];
45+
if (nums[i] + nums[j] * 3 > target) break;
46+
if (subSum + 2 * max < target) {
47+
while (nums[j] == nums[++j] && j < len - 2) ;
48+
continue;
49+
}
50+
51+
int left = j + 1, right = len - 1;
52+
while (left < right) {
53+
int sum = subSum + nums[left] + nums[right];
54+
if (sum == target) {
55+
res.add(Arrays.asList(nums[i], nums[j], nums[left], nums[right]));
56+
while (nums[left] == nums[++left] && left < right);
57+
while (nums[right] == nums[--right] && left < right);
58+
} else if (sum < target) ++left;
59+
else --right;
60+
}
61+
while (nums[j] == nums[++j] && j < len - 2) ;
62+
}
63+
while (nums[i] == nums[++i] && i < len - 3) ;
64+
}
65+
return res;
66+
}
67+
}
68+
```
69+
70+
71+
## 思路 1
72+
73+
从 [Two Sum][001]、[3Sum][015] 到现在的 4Sum，其实都是把高阶降为低阶，那么我们就可以写出 kSum 的函数来对其进行降阶处理，降到 2Sum 后那么我们就可以对其进行最后的判断了，代码如下所示，也终也做了相应的优化和去重。
74+
75+
```java
76+
class Solution {
77+
public List<List<Integer>> fourSum(int[] nums, int target) {
78+
Arrays.sort(nums);
79+
int len = nums.length;
80+
if (len < 4) return Collections.emptyList();
81+
int max = nums[len - 1];
82+
if (4 * max < target) return Collections.emptyList();
83+
return kSum(nums, 0, 4, target);
84+
}
85+
86+
private List<List<Integer>> kSum(int[] nums, int start, int k, int target) {
87+
List<List<Integer>> res = new ArrayList<>();
88+
if (k == 2) {
89+
int left = start, right = nums.length - 1;
90+
while (left < right) {
91+
int sum = nums[left] + nums[right];
92+
if (sum == target) {
93+
List<Integer> twoSum = new LinkedList<>();
94+
twoSum.add(nums[left]);
95+
twoSum.add(nums[right]);
96+
res.add(twoSum);
97+
while (nums[left] == nums[++left] && left < right) ;
98+
while (nums[right] == nums[--right] && left < right) ;
99+
} else if (sum < target) ++left;
100+
else --right;
101+
}
102+
} else {
103+
int i = start, end = nums.length - (k - 1), max = nums[nums.length - 1];
104+
while (i < end) {
105+
if (nums[i] * k > target) return res;
106+
if (nums[i] + (k - 1) * max < target) {
107+
while (nums[i] == nums[++i] && i < end) ;
108+
continue;
109+
}
110+
List<List<Integer>> temp = kSum(nums, i + 1, k - 1, target - nums[i]);
111+
for (List<Integer> t : temp) {
112+
t.add(0, nums[i]);
113+
}
114+
res.addAll(temp);
115+
while (nums[i] == nums[++i] && i < end) ;
116+
}
117+
}
118+
return res;
119+
}
120+
}
121+
```
122+
123+
124+
125+
## 结语
126+
127+
如果你同我一样热爱数据结构、算法、LeetCode，可以关注我 GitHub 上的 LeetCode 题解：[awesome-java-leetcode][ajl]
128+
129+
130+
131+
[001]: https://github.com/Blankj/awesome-java-leetcode/blob/master/note/001/README.md
132+
[015]: https://github.com/Blankj/awesome-java-leetcode/blob/master/note/015/README.md
133+
[title]: https://leetcode.com/problems/4sum
134+
[ajl]: https://github.com/Blankj/awesome-java-leetcode

‎src/com/blankj/medium/_018/Solution.java

Copy file name to clipboard
+105Lines changed: 105 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,105 @@
1+
package com.blankj.medium._018;
2+
3+
import java.util.ArrayList;
4+
import java.util.Arrays;
5+
import java.util.Collections;
6+
import java.util.LinkedList;
7+
import java.util.List;
8+
9+
/**
10+
* <pre>
11+
* author: Blankj
12+
* blog : http://blankj.com
13+
* time : 2018/01/30
14+
* desc :
15+
* </pre>
16+
*/
17+
public class Solution {
18+
// public List<List<Integer>> fourSum(int[] nums, int target) {
19+
// List<List<Integer>> res = new ArrayList<>();
20+
// int len = nums.length;
21+
// if (len < 4) return res;
22+
// Arrays.sort(nums);
23+
// int max = nums[len - 1];
24+
// if (4 * max < target) return res;
25+
// for (int i = 0; i < len - 3;) {
26+
// if (nums[i] * 4 > target) break;
27+
// if (nums[i] + 3 * max < target) {
28+
// while (nums[i] == nums[++i] && i < len - 3) ;
29+
// continue;
30+
// }
31+
//
32+
// for (int j = i + 1; j < len - 2;) {
33+
// int subSum = nums[i] + nums[j];
34+
// if (nums[i] + nums[j] * 3 > target) break;
35+
// if (subSum + 2 * max < target) {
36+
// while (nums[j] == nums[++j] && j < len - 2) ;
37+
// continue;
38+
// }
39+
//
40+
// int left = j + 1, right = len - 1;
41+
// while (left < right) {
42+
// int sum = subSum + nums[left] + nums[right];
43+
// if (sum == target) {
44+
// res.add(Arrays.asList(nums[i], nums[j], nums[left], nums[right]));
45+
// while (nums[left] == nums[++left] && left < right);
46+
// while (nums[right] == nums[--right] && left < right);
47+
// } else if (sum < target) ++left;
48+
// else --right;
49+
// }
50+
// while (nums[j] == nums[++j] && j < len - 2) ;
51+
// }
52+
// while (nums[i] == nums[++i] && i < len - 3) ;
53+
// }
54+
// return res;
55+
// }
56+
57+
public List<List<Integer>> fourSum(int[] nums, int target) {
58+
Arrays.sort(nums);
59+
int len = nums.length;
60+
if (len < 4) return Collections.emptyList();
61+
int max = nums[len - 1];
62+
if (4 * max < target) return Collections.emptyList();
63+
return kSum(nums, 0, 4, target);
64+
}
65+
66+
private List<List<Integer>> kSum(int[] nums, int start, int k, int target) {
67+
List<List<Integer>> res = new ArrayList<>();
68+
if (k == 2) {
69+
int left = start, right = nums.length - 1;
70+
while (left < right) {
71+
int sum = nums[left] + nums[right];
72+
if (sum == target) {
73+
List<Integer> twoSum = new LinkedList<>();
74+
twoSum.add(nums[left]);
75+
twoSum.add(nums[right]);
76+
res.add(twoSum);
77+
while (nums[left] == nums[++left] && left < right) ;
78+
while (nums[right] == nums[--right] && left < right) ;
79+
} else if (sum < target) ++left;
80+
else --right;
81+
}
82+
} else {
83+
int i = start, end = nums.length - (k - 1), max = nums[nums.length - 1];
84+
while (i < end) {
85+
if (nums[i] * k > target) return res;
86+
if (nums[i] + (k - 1) * max < target) {
87+
while (nums[i] == nums[++i] && i < end) ;
88+
continue;
89+
}
90+
List<List<Integer>> temp = kSum(nums, i + 1, k - 1, target - nums[i]);
91+
for (List<Integer> t : temp) {
92+
t.add(0, nums[i]);
93+
}
94+
res.addAll(temp);
95+
while (nums[i] == nums[++i] && i < end) ;
96+
}
97+
}
98+
return res;
99+
}
100+
101+
public static void main(String[] args) {
102+
Solution solution = new Solution();
103+
System.out.println(solution.fourSum(new int[]{1, 0, -1, 0, -2, 2}, 0));
104+
}
105+
}

0 commit comments

Comments
0 (0)
Morty Proxy This is a proxified and sanitized view of the page, visit original site.