【Leetcode】18.四数之和

18. 四数之和

题目

给定一个包含 n 个整数的数组 nums 和一个目标值 target，判断 nums 中是否存在四个元素 a，b，c 和 d ，使得 a + b + c + d 的值与 target 相等？找出所有满足条件且不重复的四元组。

注意：

答案中不可以包含重复的四元组。

示例：
给定数组 nums = [1, 0, -1, 0, -2, 2]，和 target = 0。
满足要求的四元组集合为：
[
    [-1,  0, 0, 1],
    [-2, -1, 1, 2],
    [-2,  0, 0, 2]
]

方法

思路类似15.三数之和

  • 第一层循环固定第一个数，然后去遍历其他三个数
  • 第二层循环固定第二个数，然后去遍历最后两个数
  • 通过双指针法找出最后两个数
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
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
public List<List<Integer>> fourSum(int[] nums,int target){
    List<List<Integer>> res = new ArrayList<>(); 
    if(nums==null||nums.length<4){
        return res;
    }
    Arrays.sort(nums);
    //定义4个指针i，j，L，R
    //i从0开始遍历，用于固定第一个数。j从i+1开始遍历，用于固定第二个数。
    //L和R作为双指针，L指向j+1，R指向数组最右端，用于找出最后两个数
    for(int i = 0; i < nums.length-3; i++){
        if(i > 0 && nums[i] == nums[i-1]){
            continue;
        }
        //计算当前前四个元素的最小值，因为已经排好序，如果最小值比目标值大，说明不会找到符合条件的四个数
        int min1 = nums[i] + nums[i+1] + nums[i+2] + nums[i+3];
        if(min1 > target){
            break;
        }
        //计算当前最后四个元素的最大值，因为已经排好序，如果最大值比目标值小，说明以目前i的位置不会找到符合条件的四个数，忽略
        int max1 = nums[i] + nums[nums.length-1] + nums[nums.length-2] + nums[nums.length-3];
        if(max1 < target){
            continue;
        }
        //第二重循环用和第一重循环类似的逻辑固定第二个数的同时，用双指针去找最后两个数
        for(int j = i + 1; j < nums.length-2; j++){
            if(j > i + 1 && nums[j] == nums[j-1]){
                continue;
            }
            //定义双指针
            int L = j + 1;
            int R = nums.length - 1;
            int min = nums[i] + nums[j] + nums[L] + nums[L+1];
            if(min > target){
                continue;
            }
            int max = nums[i] + nums[j] + nums[R] + nums[R-1];
            if(max < target){
                continue;
            }
            //双指针法找剩下的两个数
            while (L < R){
                int sum = nums[i] + nums[j] + nums[L] + nums[R];
                if(sum == target){
                    res.add(Arrays.asList(nums[i], nums[j], nums[L], nums[R]));
                    while(L < R && nums[L] == nums[L+1]){
                        L++;
                    }
                    while(L < R && j < R && nums[R]==nums[R-1]){
                        R--;
                    }
                    L++;
                    R--;
                }
                else if(sum < target)
                    L++;
                else
                    R--;
            }
        }
    }
    return res;
}