四数之和

发表于 更新于 分类于

算法-四数之和

背景

  • 算法–四数之和

  • 博主以代码随想录算法公开课进行学习

题目

  • 题意：给定一个包含 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] ]

思路

  • 这道题是经典的「N 数之和」问题，核心思路是排序 + 双指针，通过降维将四数之和转化为三数之和，再转化为两数之和，同时通过剪枝和去重避免重复结果：
    • 排序：对数组排序
    • 俩层循环固定前俩个数
    • 双指针找后俩个数
    • 剪枝优化
    • 去重

代码

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
63
64
65
66
67
68
69
70
71
import java.util.*;

public class Solution {
    public List<List<Integer>> fourSum(int[] nums, int target) {
        // 结果集初始化
        List<List<Integer>> result = new ArrayList<>();
        // 边界条件：数组长度小于4，直接返回空结果
        if (nums == null || nums.length < 4) {
            return result;
        }
        
        // 1. 排序数组（核心前提）
        Arrays.sort(nums);
        
        // 2. 第一层循环：固定第一个数 nums[k]
        for (int k = 0; k < nums.length - 3; k++) {
            // 剪枝1：如果当前数大于target且非负，后续数更大，不可能凑出target，直接终止循环
            if (nums[k] > target && nums[k] >= 0) {
                break;
            }
            // 去重1：跳过和前一个数重复的nums[k]（避免重复四元组）
            if (k > 0 && nums[k] == nums[k - 1]) {
                continue;
            }
            
            // 3. 第二层循环：固定第二个数 nums[i]
            for (int i = k + 1; i < nums.length - 2; i++) {
                // 剪枝2：前两个数的和大于target且非负，后续数更大，终止内层循环
                if (nums[k] + nums[i] > target && nums[k] + nums[i] >= 0) {
                    break;
                }
                // 去重2：跳过和前一个数重复的nums[i]（注意i的起始是k+1，所以去重条件是i > k+1）
                if (i > k + 1 && nums[i] == nums[i - 1]) {
                    continue;
                }
                
                // 4. 双指针：找后两个数 nums[left] 和 nums[right]
                int left = i + 1;
                int right = nums.length - 1;
                while (right > left) {
                    // 用long避免int溢出（关键！比如大数相加会超出int范围）
                    long sum = (long) nums[k] + nums[i] + nums[left] + nums[right];
                    
                    if (sum > target) {
                        // 和太大，右指针左移（减小和）
                        right--;
                    } else if (sum < target) {
                        // 和太小，左指针右移（增大和）
                        left++;
                    } else {
                        // 5. 找到符合条件的四元组，加入结果集
                        result.add(Arrays.asList(nums[k], nums[i], nums[left], nums[right]));
                        
                        // 去重3：跳过重复的nums[right]
                        while (right > left && nums[right] == nums[right - 1]) {
                            right--;
                        }
                        // 去重4：跳过重复的nums[left]
                        while (right > left && nums[left] == nums[left + 1]) {
                            left++;
                        }
                        
                        // 6. 双指针同时移动，找下一组可能的数
                        right--;
                        left++;
                    }
                }
            }
        }
        return result;
    }

总结

  • N 数之和问题均可通过「排序 + 双指针」降维解决（三数之和是一层循环 + 双指针，四数之和是两层循环 + 双指针）。