哈希算法题目：四数之和 题目描述 给定一个由整数组成的数组 nums 和一个目标整数 target ，请你找出并返回所有不重复的四元组 [nums[a], nums[b], nums[c], nums[d]] ，使得： 它们的和等于 target （即 nums[a] + nums[b] + nums[c] + nums[d] == target ）。 需满足 0 <= a < b < c < d < nums.length 。 返回的四元组之间不能重复，顺序可以任意。 示例 输入：nums = [ 1, 0, -1, 0, -2, 2 ]，target = 0 输出：[ [ -2, -1, 1, 2], [ -2, 0, 0, 2], [ -1, 0, 0, 1] ] 解释：四元组需和为0，且不重复。 解题过程循序渐进讲解 步骤1：问题理解与初步思路 这是“两数之和”和“三数之和”问题的扩展。最直接的方法是四重循环遍历所有可能的四元组，检查其和是否等于 target ，时间复杂度为 O(n⁴)，在数据量较大时不可行。我们需要更高效的解法，核心目标是 降低时间复杂度 并 避免重复结果 。 步骤2：排序与去重思路 为了便于去重和优化搜索，我们可以先对数组排序。排序后，相同的数字会相邻，这样在遍历时可以通过跳过重复值来避免重复的四元组。排序的时间复杂度为 O(n log n)，不影响整体效率。 步骤3：固定两层循环+双指针法 我们可以将问题转化为“两数之和”的变种： 使用两层外层循环分别固定前两个数 nums[i] 和 nums[j] （i < j）。 对于剩下的部分，用双指针法寻找后两个数 nums[left] 和 nums[right] ，使得四数之和为 target 。 具体过程： 排序数组。 第一层循环遍历 i 从 0 到 n-4。 第二层循环遍历 j 从 i+1 到 n-3。 在子数组 [j+1, n-1] 上设置双指针 left = j+1 ， right = n-1 。 计算当前四数之和 sum = nums[i] + nums[j] + nums[left] + nums[right] 。 如果 sum == target ，记录四元组，并移动双指针跳过重复值。 如果 sum < target ，则 left++ （因为数组已排序，需要增大和）。 如果 sum > target ，则 right-- （需要减小和）。 步骤4：去重细节 去重是关键，需在三个位置进行： 外层循环 i ：如果 i > 0 且 nums[i] == nums[i-1] ，则跳过本次循环，避免重复的 nums[i] 。 内层循环 j ：如果 j > i+1 且 nums[j] == nums[j-1] ，则跳过，避免重复的 nums[j] 。 双指针部分：当找到和为 target 的四元组后，在移动 left 和 right 时，跳过所有与当前值相同的元素。 步骤5：提前终止优化 由于数组已排序，我们可以通过判断当前最小可能和与最大可能和来提前终止无效搜索： 在固定 i 和 j 后，当前最小四数和为 nums[i] + nums[j] + nums[left] + nums[left+1] （如果存在），如果这个值大于 target ，则后续更大的 j 或 i 必然更大，可直接跳出循环。 当前最大四数和为 nums[i] + nums[j] + nums[right-1] + nums[right] ，如果这个值小于 target ，则当前 j 过小，可继续增加 j 尝试。 步骤6：算法复杂度分析 时间复杂度：O(n³)，其中两层循环 O(n²)，双指针 O(n)，总体 O(n³)。 空间复杂度：O(1)（忽略存储结果的空间）或 O(n)（如果考虑排序的栈空间）。 步骤7：示例推导 以 nums = [ 1, 0, -1, 0, -2, 2 ]，target = 0 为例： 排序后数组：[ -2, -1, 0, 0, 1, 2 ]。 固定 i=0（-2），j=1（-1），则 left=2（0），right=5（2），计算和 -1，小于0，left++。 left=3（0），和 -1，仍小于0，left++。 left=4（1），和 0，找到四元组 [ -2, -1, 1, 2 ]，记录后 left 和 right 移动并去重。 继续直到遍历所有可能。 最终输出 即为 [ [ -2, -1, 1, 2], [ -2, 0, 0, 2], [ -1, 0, 0, 1] ]。 这个解法结合了排序、双指针和去重技巧，是解决“四数之和”问题的标准高效方法。