LeetCode 18题"四数之和"要求我们在一个包含n个整数的数组中，找出所有不重复的四元组(a,b,c,d)，使得它们的和等于目标值target。这个问题看似只是"三数之和"的简单扩展，但实际操作中会遇到更多细节陷阱。
先看题目给出的关键约束：
数组长度n可以达到200（比三数之和的1000小，但四元组组合复杂度更高）
答案中不允许包含重复的四元组
数组元素可能包含负数和零
目标值target可以是任意整数（包括负数）
最直观的暴力解法是四层嵌套循环，时间复杂度达到O(n⁴)，这在n=200时会产生200⁴=1.6亿次运算，显然会超时。因此我们需要更高效的解法。
排序+双指针解法的核心思路
四数之和的最优解法依然是排序+双指针的组合策略，但比三数之和多了一层循环控制。基本思路是：
先对数组进行排序（O(n log n)时间）
固定两个数（通过两层循环）
用双指针寻找剩下的两个数，将问题降为两数之和问题
全程进行去重处理，避免重复四元组
上图清晰展示了算法的执行流程：
外层i循环固定第一个数
中层j循环固定第二个数
内层left和right双指针从两端向中间移动，寻找和为target-nums[i]-nums[j]的两个数
每次找到符合条件的四元组后，进行去重操作并记录结果
这种解法的时间复杂度是O(n³)，空间复杂度是O(1)（不考虑存储结果的空间）。
Python实现代码与详细注释
def fourSum(nums, target):# 结果列表result =# 获取数组长度n = len(nums)# 数组长度小于4时直接返回空列表if n < 4:return result# 对数组进行排序，为双指针和去重做准备nums.sort()# 外层循环：固定第一个数for i in range(n - 3):# 第一个数去重if i > 0 and nums[i] == nums[i - 1]:continue# 优化：如果当前最小的四数之和已经大于target，无需继续if nums[i] + nums[i+1] + nums[i+2] + nums[i+3] > target:break# 优化：如果当前最大的四数之和还小于target，跳过当前iif nums[i] + nums[n-3] + nums[n-2] + nums[n-1] < target:continue# 中层循环：固定第二个数for j in range(i + 1, n - 2):# 第二个数去重if j > i + 1 and nums[j] == nums[j - 1]:continue# 优化：如果当前最小的四数之和已经大于target，无需继续if nums[i] + nums[j] + nums[j+1] + nums[j+2] > target:break# 优化：如果当前最大的四数之和还小于target，跳过当前jif nums[i] + nums[j] + nums[n-2] + nums[n-1] < target:continue# 双指针初始化left = j + 1 # 左指针从j+1开始right = n - 1 # 右指针从数组末尾开始# 双指针寻找剩下的两个数while left < right:current_sum = nums[i] + nums[j] + nums[left] + nums[right]# 找到符合条件的四元组if current_sum == target:# 添加到结果列表result.append([nums[i], nums[j], nums[left], nums[right]])# 左指针去重while left < right and nums[left] == nums[left + 1]:left += 1# 右指针去重while left < right and nums[right] == nums[right - 1]:right -= 1# 移动双指针left += 1right -= 1# 当前和小于目标值，左指针右移增大和elif current_sum < target:left += 1# 当前和大于目标值，右指针左移减小和else:right -= 1return result
去重逻辑深度分析
四数之和问题中最容易出错的部分就是去重逻辑。与三数之和相比，四数之和需要对两个固定指针(i和j)都进行去重处理，这增加了复杂度。
四种指针的去重策略
i指针去重：
if i > 0and nums[i] == nums[i - 1]: continue
注意i必须从1开始比较，避免越界。当i与i-1相等时跳过当前值。
j指针去重：
if j > i + 1and nums[j] == nums[j - 1]: continue
j的去重起始条件是j > i + 1，确保j至少从i+1的下一个位置开始比较。
left指针去重：
while left < right and nums[left] == nums[left + 1]: left += 1 left += 1# 最后再移动一次指针
找到符合条件的四元组后，将left移到最后一个重复元素的位置，然后再+1。
right指针去重：
while left < right and nums[right] == nums[right - 1]: right -= 1 right -= 1# 最后再移动一次指针
类似地，将right移到最后一个重复元素的位置，然后再-1。
去重的常见错误与解决方案
错误1：在找到目标和之前就进行去重
# 错误示例while left < right and nums[left] == nums[left + 1]: left += 1
解决方案：只有在找到符合条件的四元组后才进行去重操作
错误2：去重后忘记移动指针
# 错误示例while left < right and nums[left] == nums[left + 1]: left += 1# 缺少 left += 1
解决方案：去重循环后必须手动移动一次指针
错误3：i和j的去重条件不正确
# 错误示例if nums[i] == nums[i + 1]: # 应该和i-1比较而不是i+1continue
解决方案：i应该和i-1比较，j应该和j-1比较
边界情况处理策略
四数之和问题有许多边界情况需要特殊处理，否则容易导致错误或超时：
1. 数组长度不足4的情况
if n < 4: return result
直接返回空列表，因为无法组成四元组。
2. 整数溢出问题
在Java等语言中，四个整数相加可能会超出int范围，需要使用long类型：
longcurrentSum= (long) nums[i] + nums[j] + nums[left] + nums[right];
3. 提前终止循环的优化
# 最小四数之和大于target，后续不可能有解if nums[i] + nums[i+1] + nums[i+2] + nums[i+3] > target: break# 当前i对应的最大四数之和小于target，跳过当前iif nums[i] + nums[n-3] + nums[n-2] + nums[n-1] < target: continue
这两个优化可以大幅减少不必要的循环，特别是在数组元素较大或较小时。
4. 处理重复元素密集的数组
当数组中有大量重复元素时，去重逻辑尤为重要。例如数组[0,0,0,0,0]，target=0，正确答案应该只有一个四元组[0,0,0,0]。
5. 处理target为负数的情况
与三数之和不同，四数之和的target可以是负数，这时候不能简单地通过判断nums[i] > target就跳出循环，因为后续的负数相加可能会使总和减小到target。
k数之和的通用解题思路
四数之和是k数之和问题的一个特例，我们可以将其推广为更通用的k数之和解法。
k数之和的递归解法
基本思路是通过递归将k数之和问题逐步降为(k-1)数之和、(k-2)数之和，直到2数之和问题，然后用双指针求解：
def kSum(nums, target, k):# 排序数组nums.sort()# 结果列表result = []# 调用递归函数backtrack(nums, target, k, 0, [], result)return resultdef backtrack(nums, target, k, start, path, result):# 递归终止条件：k=2时使用双指针if k == 2:left, right = start, len(nums) - 1while left < right:current_sum = nums[left] + nums[right]if current_sum == target:result.append(path + [nums[left], nums[right]])# 去重while left < right and nums[left] == nums[left + 1]:left += 1while left < right and nums[right] == nums[right - 1]:right -= 1left += 1right -= 1elif current_sum < target:left += 1else:right -= 1return# 递归处理k>2的情况for i in range(start, len(nums) - k + 1):# 去重if i > start and nums[i] == nums[i - 1]:continue# 优化：如果当前最小的k数之和已经大于target，无需继续if sum(nums[i:i+k]) > target:break# 优化：如果当前最大的k数之和还小于target，跳过当前iif nums[i] + sum(nums[-k+1:]) < target:continue# 递归调用，k减1，start设为i+1，路径添加当前元素backtrack(nums, target - nums[i], k - 1, i + 1, path + [nums[i]], result)
k数之和的时间复杂度分析
排序时间：O(n log n)
递归调用次数：O(n^(k-1))，对于四数之和是O(n³)
双指针部分：O(n)
总时间复杂度：O(n log n + n^(k-1))
当k=2时，时间复杂度为O(n log n)；当k=3时，为O(n²)；当k=4时，为O(n³)，依此类推。
k数之和的空间复杂度分析
递归调用栈深度：O(k)
存储结果的空间：O(C(n,k))，最坏情况下是O(n^k)
总空间复杂度：O(n^k)
算法优化技巧
为了进一步提高四数之和算法的效率，可以采用以下优化技巧：
1. 提前终止循环
在每层循环中，如果当前最小可能的和已经大于target，或者当前最大可能的和还小于target，可以直接终止或跳过当前循环：
2. 处理大规模重复元素
当数组中存在大量重复元素时，可以通过计数来减少循环次数：
然后在循环时考虑每个数字的出现次数，避免对重复元素进行多次循环。
3. 剪枝优化
在递归实现的k数之和中，可以通过剪枝进一步减少不必要的计算：
总结与拓展
四数之和问题是对排序+双指针技巧的进一步深化应用，通过固定两个数并使用双指针寻找另外两个数，将时间复杂度从O(n⁴)降低到O(n³)。
关键知识点回顾
排序+双指针是解决n数之和问题的通用方法
去重逻辑是保证结果正确性的关键，需要对四个指针分别处理
边界情况处理直接影响算法的健壮性
提前终止循环可以显著提高算法效率
k数之和可以通过递归降维为2数之和问题
相关题目推荐
LeetCode 1 两数之和：基础的两数之和问题，可使用哈希表解法
LeetCode 15 三数之和：四数之和的简化版，固定一个数+双指针
LeetCode 16 最接近的三数之和：类似问题，但要求找到最接近目标的和
LeetCode 454 四数相加II：四个数组的四数之和问题，可使用哈希表优化
算法思维拓展
四数之和问题体现了降维思想——将高维问题转化为低维问题求解。这种思想在算法设计中非常重要：
空间降维：如将二维数组问题转化为一维数组问题
时间降维：如将四重循环降为三重循环
问题降维：如将k数之和降为2数之和
掌握降维思想可以帮助我们解决更多复杂问题，提高算法效率。
通过本文的学习，相信你已经掌握了四数之和问题的核心解法和优化技巧。这个问题虽然看似简单，但其中包含了丰富的算法思想和编程细节，值得我们深入研究和思考。