Leetcode 四数之和
当然可以！下面是这道题（LeetCode 18: 四数之和）的思路总览模板答案，适用于笔试、面试或者写题解时的标准答题格式👇
🧩 LeetCode 18. 四数之和 —— 思路总览模板答案
✅ 题目描述简要
给定一个整数数组 nums 和一个目标值 target，找出所有不重复的四元组 [a, b, c, d]，使得：
nums[a] + nums[b] + nums[c] + nums[d] == target
要求：
- 四元组元素的下标不重复
- 四元组值不能重复（顺序无关）
🔍 解题思路
1. 排序数组
首先将数组 nums 升序排序，便于后续使用双指针，并且方便跳过重复元素。
2. 枚举前两个数 + 双指针找后两个数
- 固定前两个数
nums[i]和nums[j] - 在剩余部分使用双指针
left和right，寻找符合条件的另外两个数
3. 跳过重复元素
- 对于每一层循环（i, j）和每次指针移动（left, right），都要跳过相同的数值，确保不出现重复的四元组
4. 使用 long 防止整型溢出
nums[i] + nums[j] + nums[left] + nums[right]可能超出int范围，因此建议用long存储临时和
🧠 算法复杂度
-
时间复杂度：O(n³)
三重循环（两层 + 双指针）枚举所有可能组合 -
空间复杂度：O(1)
只用了常数级额外空间（不算返回结果）
💡 关键技巧总结
- 排序数组：便于双指针和去重操作
- 双指针：利用有序数组快速找到两数之和
- 去重处理：防止重复答案（i、j、left、right层层去重）
- long 类型：规避溢出风险
java solution
class Solution {
public List<List<Integer>> fourSum(int[] nums, int target) {
List<List<Integer>> result = new ArrayList<>();
//首先进行排序
Arrays.sort(nums);
int n = nums.length;
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, right = n - 1;
while(left < right) {
//先计算四数之和
long sum = (long) nums[i] + nums[j] + nums[left] + nums[right];
if(sum == target) {
result.add(Arrays.asList(nums[i], nums[j], nums[left], nums[right]));
//继续去重
while(left < right && nums[left] == nums[left + 1]) left++;
while(left < right && nums[right] == nums[right - 1] ) right--;
//此时left和right仍然需要移动一位,因为上面的去重只是移动到连续重复的最后一个字符
left++;
right--;
} else if(sum < target){
left++;
} else {
right--;
}
}
}
}
return result;
}
}
当然可以！我们来一步步详细剖析这段 Java 代码的 算法思想和实现细节。目标是解决 LeetCode 第 18 题 —— 四数之和（4Sum）问题：
🧠 题目核心思想
给定一个数组 nums 和一个目标值 target，我们需要找出所有 不重复的四元组 [a, b, c, d]，使得：
nums[a] + nums[b] + nums[c] + nums[d] == target
✨ 算法核心步骤（排序 + 双指针）
我们用一种 类似“三数之和”（3Sum） 的方式来解决这个问题，只不过是套两层循环 + 双指针。
🧩 代码讲解
public List<List<Integer>> fourSum(int[] nums, int target) {
我们定义一个返回值为 List 的函数，返回所有不重复的四元组。
List<List<Integer>> result = new ArrayList<>();
Arrays.sort(nums); // 排序，方便后面双指针处理和去重
对数组进行排序是关键，排序后我们就可以利用双指针进行查找，同时能方便地跳过重复值。
int n = nums.length;
for (int i = 0; i < n - 3; i++) {
if (i > 0 && nums[i] == nums[i - 1]) continue; // 去重
第一层循环，选第一个数 nums[i]。去重防止同样的开头重复出现。
for (int j = i + 1; j < n - 2; j++) {
if (j > i + 1 && nums[j] == nums[j - 1]) continue; // 去重
第二层循环，选第二个数 nums[j]，同样做去重。
int left = j + 1, right = n - 1;
这时候，问题变成了：在 nums[j+1] ~ nums[n-1] 中找两个数，使得四个数的和等于 target。这正是双指针的用武之地。
while (left < right) {
long sum = (long) nums[i] + nums[j] + nums[left] + nums[right];
这里我们用了 long 来存储和，是为了避免大整数相加时溢出。
if (sum == target) {
result.add(Arrays.asList(nums[i], nums[j], nums[left], nums[right]));
如果找到满足条件的四元组，加入结果集。
while (left < right && nums[left] == nums[left + 1]) left++; // 去重
while (left < right && nums[right] == nums[right - 1]) right--; // 去重
left++;
right--;
找到一个解后，我们继续往下找新的解，但要跳过相同的值（防止重复解）。
} else if (sum < target) {
left++; // 和太小，左边往右移动
} else {
right--; // 和太大，右边往左移动
}
如果当前和小于目标值，我们就让左指针右移，反之则右指针左移。
✅ 最终返回结果
return result;
}
📈 时间复杂度分析
- 外层两层循环：
O(n^2) - 内层双指针扫描：
O(n) - 所以总时间复杂度是：
O(n^3)，比暴力穷举O(n^4)快了很多。
🧹 去重机制详解
- 第1个数
i和第2个数j：如果跟前一个一样，就跳过 - 第3和第4个数：用
while跳过重复值（排序保证相同值相邻）
🛡️ 为何使用 long 来存和？
避免整型溢出！比如 Integer.MAX_VALUE + Integer.MAX_VALUE 就会出错，所以强转为 long 保险。