Movatterモバイル変換

[0]ホーム
URL:

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

 Sign up
Appearance settings

Commitd818aad

Browse files
committed
add: 018
1 parent00e6bad commitd818aad

File tree

3 files changed

+241
-0
lines changed

3 files changed

+241
-0
lines changed

‎README.md

Lines 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

Lines 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+
classSolution {
29+
publicList<List<Integer>>fourSum(int[]nums,inttarget) {
30+
List<List<Integer>> res=newArrayList<>();
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+
}elseif (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+
classSolution {
77+
publicList<List<Integer>>fourSum(int[]nums,inttarget) {
78+
Arrays.sort(nums);
79+
int len= nums.length;
80+
if (len<4)returnCollections.emptyList();
81+
int max= nums[len-1];
82+
if (4* max< target)returnCollections.emptyList();
83+
return kSum(nums,0,4, target);
84+
}
85+
86+
privateList<List<Integer>>kSum(int[]nums,intstart,intk,inttarget) {
87+
List<List<Integer>> res=newArrayList<>();
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=newLinkedList<>();
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+
}elseif (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
Lines changed: 105 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,105 @@
1+
packagecom.blankj.medium._018;
2+
3+
importjava.util.ArrayList;
4+
importjava.util.Arrays;
5+
importjava.util.Collections;
6+
importjava.util.LinkedList;
7+
importjava.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+
publicclassSolution {
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+
publicList<List<Integer>>fourSum(int[]nums,inttarget) {
58+
Arrays.sort(nums);
59+
intlen =nums.length;
60+
if (len <4)returnCollections.emptyList();
61+
intmax =nums[len -1];
62+
if (4 *max <target)returnCollections.emptyList();
63+
returnkSum(nums,0,4,target);
64+
}
65+
66+
privateList<List<Integer>>kSum(int[]nums,intstart,intk,inttarget) {
67+
List<List<Integer>>res =newArrayList<>();
68+
if (k ==2) {
69+
intleft =start,right =nums.length -1;
70+
while (left <right) {
71+
intsum =nums[left] +nums[right];
72+
if (sum ==target) {
73+
List<Integer>twoSum =newLinkedList<>();
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+
}elseif (sum <target) ++left;
80+
else --right;
81+
}
82+
}else {
83+
inti =start,end =nums.length - (k -1),max =nums[nums.length -1];
84+
while (i <end) {
85+
if (nums[i] *k >target)returnres;
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+
returnres;
99+
}
100+
101+
publicstaticvoidmain(String[]args) {
102+
Solutionsolution =newSolution();
103+
System.out.println(solution.fourSum(newint[]{1,0, -1,0, -2,2},0));
104+
}
105+
}

0 commit comments

Comments
 (0)
[8]ページ先頭
©2009-2025 Movatter.jp