LeetCode 18. 四数之和

Categories:

题目描述
思路分析
1. 解法一：排序 + 双指针（推荐）
相似题目

题目描述

✅ 18. 四数之和

思路分析

解法一：排序 + 双指针（推荐）

核心思路：

先对数组排序，将无序问题转化为有序问题，方便去重和双指针移动。

外层两重循环固定前两个数 nums[i] 和 nums[j]，内层用双指针 left、right 夹逼查找后两个数。

每次找到满足条件的四元组后，同时向内移动两个指针，并跳过重复值。

对 i 和 j 分别进行去重：跳过与前一个相同的元素，避免结果集重复。

复杂度分析：

时间复杂度：O(n³)，其中 n 表示数组长度。两层固定循环 O(n²)，内层双指针 O(n)。

空间复杂度：O(log n)，其中 log n 为排序所用的递归栈空间。

class Solution {
    public List<List<Integer>> fourSum(int[] nums, int target) {
        List<List<Integer>> res = new ArrayList<>();
        int n = nums.length;
        if (n < 4) {
            return res;
        }
        // 排序，便于去重和双指针
        Arrays.sort(nums);
        for (int i = 0; i < n - 3; i++) {
            // 跳过第一个数的重复值
            if (i > 0 && nums[i] == nums[i - 1]) {
                continue;
            }
            for (int j = i + 1; j < n - 2; j++) {
                // 跳过第二个数的重复值
                if (j > i + 1 && nums[j] == nums[j - 1]) {
                    continue;
                }
                int left = j + 1;
                int right = n - 1;
                while (left < right) {
                    long sum = (long) nums[i] + nums[j] + nums[left] + nums[right];
                    if (sum == target) {
                        res.add(Arrays.asList(nums[i], nums[j], nums[left], nums[right]));
                        // 跳过 left 的重复值
                        while (left < right && nums[left] == nums[left + 1]) {
                            left++;
                        }
                        // 跳过 right 的重复值
                        while (left < right && nums[right] == nums[right - 1]) {
                            right--;
                        }
                        left++;
                        right--;
                    } else if (sum < target) {
                        left++;
                    } else {
                        right--;
                    }
                }
            }
        }
        return res;
    }
}

func fourSum(nums []int, target int) [][]int {
	n := len(nums)
	var res [][]int
	if n < 4 {
		return res
	}

	// 排序，便于去重和双指针
	sort.Ints(nums)

	for i := 0; i < n-3; i++ {
		// 跳过第一个数的重复值
		if i > 0 && nums[i] == nums[i-1] {
			continue
		}
		for j := i + 1; j < n-2; j++ {
			// 跳过第二个数的重复值
			if j > i+1 && nums[j] == nums[j-1] {
				continue
			}
			left, right := j+1, n-1
			for left < right {
				sum := nums[i] + nums[j] + nums[left] + nums[right]
				if sum == target {
					res = append(res, []int{nums[i], nums[j], nums[left], nums[right]})
					// 跳过 left 的重复值
					for left < right && nums[left] == nums[left+1] {
						left++
					}
					// 跳过 right 的重复值
					for left < right && nums[right] == nums[right-1] {
						right--
					}
					left++
					right--
				} else if sum < target {
					left++
				} else {
					right--
				}
			}
		}
	}

	return res
}

相似题目

题目	难度	考察点
1. 两数之和	简单	哈希表 / 双指针
15. 三数之和	中等	排序 + 双指针 / 去重
16. 最接近的三数之和	中等	排序 + 双指针
454. 四数相加 II	中等	哈希表 / 分组枚举
611. 有效三角形的个数	中等	排序 + 双指针
167. 两数之和 II - 输入有序数组	中等	双指针

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2026/37482392