0%

LeetCode-4Sum

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;
}
}