https://leetcode-cn.com/problems/4sum/
按照之前3Sum的思路，再加一层循环，程序如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
| class Solution {
public List<List<Integer>> fourSum(int[] nums, int target) {
List<List<Integer>> ret=new ArrayList<>();
if(nums.length<4) return ret;
Arrays.sort(nums);
for(int i=0;i<nums.length-3;i++){
if(i>0 && nums[i-1]==nums[i]) continue;
for(int j=i+1;j<nums.length-2;j++){
if(j>i+1 && nums[j-1]==nums[j]) continue;
int k=j+1,l=nums.length-1;
while(k<l){
int sum=nums[i]+nums[j]+nums[k]+nums[l];
if(sum==target){
List<Integer> li=new ArrayList<>();
li.add(nums[i]);
li.add(nums[j]);
li.add(nums[k]);
li.add(nums[l]);
ret.add(li);
int tk=nums[k],tl=nums[l];
while(tk==nums[k] && k<l) k++;
while(tl==nums[l] && k<l) l--;
}else if(sum>target){
l--;
}else{
k++;
}
}
}
}
return ret;
}
}
|
需要注意的是不要剪枝剪多了，比如之前if(nums[i]>0) break;这种都不能有，因为 target 可能小于 0。
另外，还可以根据之前2Sum的思路来写。
大概思路就是将 nums 数组中的数两两加和，放入哈希表中，然后按照 2Sum 中的方法，从哈希表中找出对应的元素，进行解析。
这里有两个技巧：添加哈希表的时候，因为有两个数字，所以使用 Integer[]进行存储，而且可能会出现多种组合，所以使用 List<>进行表示；而在查找时候，需要去重处理，因为a0<a1，而b0<b1，所以只需要使a1<b0即可。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
| public class Solution {
public List<List<Integer>> fourSum(int[] nums, int target) {
List<List<Integer>> ret=new ArrayList<>();
if(nums.length<4) return ret;
Arrays.sort(nums);
Map<Integer,List<Integer[]>> hm=new HashMap<>();
for(int i=0;i<nums.length-1;i++){
for(int j=i+1;j<nums.length;j++){
int s=nums[i]+nums[j];
if(!hm.containsKey(s)) hm.put(s,new ArrayList<Integer[]>());
hm.get(s).add(new Integer[]{i,j});
}
}
for(int i:hm.keySet()){
List<Integer[]> l1=hm.get(i);
List<Integer[]> l2=hm.get(target-i);
if(l1!=null && l2!=null){
for(Integer[] as:l1){
int a0=as[0],a1=as[1];
for(Integer[] bs:l2){
int b0=bs[0],b1=bs[1];
if(a1<b0){
List<Integer> l=new ArrayList<>();
l.add(nums[a0]);
l.add(nums[a1]);
l.add(nums[b0]);
l.add(nums[b1]);
if(!ret.contains(l)) ret.add(l);
}
}
}
}
}
return ret;
}
}
|