首页 > itarticle > leetcode 18 4sum

leetcode 18 4sum

admin 11月 14, 2020 0

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.

Note: The solution set must not contain duplicate quadruplets.

1
2
3
4
5
6
7
8
 
For example, given array S = [1, 0, -1, 0, -2, 2], and target = 0.

A solution set is:
[
  [-1,  0, 0, 1],
  [-2, -1, 1, 2],
  [-2,  0, 0, 2]
]
 
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
37
38
39
 
class  {
    public List<List<Integer>> fourSum(int[] nums, int target) {
        List<List<Integer>> ans = new ArrayList<>();
        if(nums.length < 4) return ans;
        Arrays.sort(nums);
        for(int i=0; i<nums.length-3; i++){
            if(i > 0 && nums[i] == nums[i-1])
                continue;
            for(int j = i+1; j<nums.length-2; j++){
                int start = j+1;
                int end = nums.length-1;
                if(nums[j] == nums[j-1] && j>i+1)
                  continue;  
                   while(start < end){
                       if(nums[i] +nums[j] +nums[start] + nums[end] < target){
                           start ++;
                       }
                       else if(nums[i] +nums[j] +nums[start] + nums[end] > target){
                           end --;
                       }
                       else{
                           List<Integer> t = new ArrayList<Integer>();
                           t.add(nums[i]);
                           t.add(nums[j]);
                           t.add(nums[start]);
                           t.add(nums[end]);
                           ans.add(t);
                           while(nums[start] == nums[start+1] && start+1 < end) start ++;
                           while(nums[end] == nums[end-1]&& start+1 < end) end --;
                           start ++;
                           end --;
                       }
                   }
            }
        }
        
        return ans;
    }
}
  • Generally, we can using 3sum to deal 4sum, 2sum to deal 3sum.
  • using 4 pointers to judge
  • There are some improvements which to avoid some redundent calculation.
  • Pay attention to the clause used to avoid duplicate answers.

微海报分享

近期文章

近期评论

标签

热门

文章归档

分类目录

功能