哈希算法题目：四数之和 题目描述 给定一个包含 n 个整数的数组 nums 和一个目标值 target，请你判断 nums 中是否存在四个元素 a，b，c 和 d，使得 a + b + c + d 的值与 target 相等？你需要找出所有满足条件且不重复的四元组。 注意：答案中不可以包含重复的四元组。 示例 1： 输入：nums = [ 1,0,-1,0,-2,2 ], target = 0 输出：[ [ -2,-1,1,2],[ -2,0,0,2],[ -1,0,0,1] ] 示例 2： 输入：nums = [ 2,2,2,2,2 ], target = 8 输出：[ [ 2,2,2,2] ] 解题过程循序渐进讲解 这个问题的核心挑战在于如何高效地找到所有不重复的四元组。我们将采用一种结合排序和哈希表的方法来优化查找过程。 步骤一：排序数组 首先，我们对输入的数组 nums 进行排序。排序有两个主要目的： 它使得我们能够方便地跳过重复的元素，从而避免在结果中出现重复的四元组。 它为后续使用双指针技术（虽然我们这里主要用哈希，但排序是基础）奠定了基础。 例如，对于 nums = [ 1,0,-1,0,-2,2]，排序后得到 [ -2, -1, 0, 0, 1, 2 ]。 步骤二：核心思路与哈希表的作用 我们可以将四数之和问题转化为类似“两数之和”的问题。基本思路是： 遍历数组，先固定前两个数（我们称它们为 nums[i] 和 nums[j] ）。 在固定了前两个数之后，问题就转化为：在剩下的子数组（即 j+1 到数组末尾）中，寻找两个数 nums[k] 和 nums[l] ，使得它们的和等于 target - (nums[i] + nums[j]) 。 为了高效地解决这个“两数之和”的子问题，我们可以使用一个哈希表。哈希表可以帮助我们以接近 O(1) 的时间复杂度检查某个需要的差值是否存在。 具体算法步骤： 初始化 ： 对数组 nums 进行排序。 初始化一个空列表 result 用于存放最终结果。 获取数组长度 n 。 第一层循环（固定第一个数 i） ： 使用索引 i 从 0 遍历到 n-4 （因为后面至少还需要三个数）。 关键的去重操作 ：如果 i > 0 并且 nums[i] == nums[i-1] ，说明当前数字和上一个数字相同。为了避免产生重复的四元组，我们直接跳过本次循环（ continue ）。因为以同一个数值作为第一个数，找到的组合在之前一定已经找过了。 第二层循环（固定第二个数 j） ： 在 i 固定的情况下，使用索引 j 从 i+1 遍历到 n-3 （因为后面至少还需要两个数）。 关键的去重操作 ：如果 j > i+1 并且 nums[j] == nums[j-1] ，说明当前数字和它在本次循环中的上一个数字相同。为了避免重复，我们同样跳过本次循环（ continue ）。 使用哈希表寻找后两个数 ： 在固定了 i 和 j 之后，计算剩余需要寻找的两数之和： remaining = target - nums[i] - nums[j] 。 初始化一个哈希表 seen （通常用集合 set 或字典 dict ），它的作用是记录在索引 j 之后，我们“已经见过”哪些数字。 使用索引 k 从 j+1 开始遍历到数组末尾。 计算当前我们需要寻找的另一个数： complement = remaining - nums[k] 。 检查哈希表 ：检查 complement 是否存在于哈希表 seen 中。 如果存在，说明我们找到了一组解： (nums[i], nums[j], complement, nums[k]) 。我们将这个四元组添加到 result 中。 关键的去重操作（针对后两个数） ：在添加了四元组之后，我们需要跳过所有与当前 nums[k] 相同的后续元素，以防止出现如 [x, y, a, b] 和 [x, y, a, c] （其中 b=c）这样的重复。我们可以使用一个 while 循环，让 k 自增，直到 nums[k] 不等于下一个元素的值。 无论是否找到解，我们都需要将当前的 nums[k] 加入到哈希表 seen 中，因为它可能成为后续某个 k 的 complement 。 为什么这个算法有效？ 去重 ：通过排序和跳过重复元素（在 i, j, k 的循环中），我们系统地避免了使用相同数值的不同索引来构造相同的四元组。 效率 ：排序的时间复杂度是 O(n log n)。外层双重循环是 O(n²)，内层遍历 k 也是 O(n)，但结合哈希表的查找操作（O(1)），内层循环总体可以视为 O(n)。因此，算法的总时间复杂度约为 O(n³)，但在实际中，由于跳过大量重复元素，效率尚可。空间复杂度主要是哈希表，为 O(n)。 示例推演（nums = [ 1,0,-1,0,-2,2], target=0） 排序后数组：[ -2, -1, 0, 0, 1, 2 ] i=0, nums[ i ]=-2 j=1, nums[ j ]=-1, remaining = 0 - (-2) - (-1) = 3 k=2, nums[ k ]=0, complement=3-0=3 (不在seen中), seen={0} k=3, nums[ k ]=0, complement=3-0=3 (不在seen中), seen={0} (注意，虽然值相同，但索引不同，我们仍然添加，但后续去重会处理结果) k=4, nums[ k ]=1, complement=3-1=2 (不在seen中), seen={0, 1} k=5, nums[ k]=2, complement=3-2=1 (在seen中！找到一组解 [ -2,-1,1,2 ]), 添加结果。seen={0,1,2} j=2, nums[ j ]=0, remaining=0-(-2)-0=2 k=3, nums[ k ]=0, complement=2-0=2 (不在seen中), seen={0} k=4, nums[ k ]=1, complement=2-1=1 (不在seen中), seen={0,1} k=5, nums[ k]=2, complement=2-2=0 (在seen中！找到一组解 [ -2,0,0,2 ]), 添加结果。seen={0,1,2} ... (继续遍历) 通过这种方式，我们可以找到所有不重复的四元组。