LeetCode 16最接近三数之和 | 双指针法的灵活应用引言在算法面试中最接近三数之和3Sum Closest是三数之和问题的自然延伸编号为 LeetCode 16。这道题要求在一个整数数组中找出三个数使它们的和最接近给定的目标值。与三数之和不同这里不需要精确等于目标值而是寻找最接近的组合。这种问题的实用性很强例如在数据分析中寻找最接近某个目标值的组合或者在资源分配中寻找最优搭配等场景都可能出现类似的需求。最接近三数之和问题在思路上与三数之和非常相似都采用双指针法进行求解但在具体实现上存在一些关键区别。由于不需要精确匹配算法在找到接近的组合时不需要立即停止而是继续搜索直到遍历完所有可能的情况。同时由于不需要去重代码实现反而会更加简洁一些。本文将详细分析这一问题的解决思路和实现细节。问题分析题目描述给定一个长度为 n 的整数数组 nums 和一个目标值 target从 nums 中选择三个整数 nums[i]、nums[j]、nums[k]使得 (nums[i] nums[j] nums[k]) 与 target 之间的绝对差值最小。返回这三个数的和。例如输入 nums [-1, 2, 1, -4] 和 target 1最接近的三数之和为 2因为 -1 2 1 2与 1 的差值为 1。问题特点最接近三数之和问题的核心挑战在于如何在众多可能的三元组中快速找到最接近目标值的那一个。如果采用暴力枚举所有三元组的方式时间复杂度为 O(n³)对于大规模数据显然不够高效。更重要的是由于不需要精确匹配我们无法使用哈希表等数据结构来加速查找因为哈希表通常只适用于精确匹配的场景。双指针法再次成为解决这个问题的关键技巧。排序数组后通过左右指针的动态调整可以在 O(n²) 时间复杂度内遍历所有可能的三元组。与三数之和不同的是这里不需要进行去重处理因为我们的目标是找到最接近的三数之和而不是返回所有满足条件的不重复三元组。与三数之和的对比虽然最接近三数之和和三数之和都使用双指针法解决但两者在具体实现上存在几个重要区别。首先三数之和要求精确等于零而最接近三数之和只需要接近目标值这意味着后者不需要进行复杂的去重操作。其次在指针移动策略上三数之和在找到精确匹配后仍需要继续移动指针寻找其他组合但最接近三数之和在每次比较后都需要根据当前三数之和与目标值的关系来决定指针的移动方向。从返回值来看三数之和返回一个三元组列表而最接近三数之和返回一个整数三个数的和。这个差异也影响了两道题在代码实现上的细节处理。三数之和需要记录所有满足条件的组合而最接近三数之和只需要记录当前最优的组合。算法设计排序与初始化与三数之和一样解决最接近三数之和的第一步是对数组进行排序。排序不仅为双指针的移动提供了方向性指导还能使后续的遍历过程更加高效。排序后相同或相近的元素聚集在一起这虽然对本题的去重没有直接帮助因为不需要去重但保证了双指针移动逻辑的正确性。在开始遍历之前我们需要设置初始的最优结果。一种常见的选择是将数组中最前面的三个数之和作为初始最优值。但更稳妥的做法是初始化一个很大的差值例如无穷大然后在遍历过程中不断更新。初始化时直接将 best_sum 设置为前三数之和是可以接受的因为后续一定会找到更优或相等的结果。双指针遍历外层循环遍历数组的每个元素作为三元组的第一个数内层使用双指针在剩余范围内寻找最接近 target - nums[i] 的两个数。指针初始化时left 指向 i1right 指向数组末尾。每次计算当前三数之和 current_sum nums[i] nums[left] nums[right]然后计算与目标值的差值 diff abs(current_sum - target)。根据 diff 的大小更新最优结果如果当前差值小于历史最小差值则用当前三数之和更新 best_sum。接下来根据 current_sum 与 target 的关系决定指针的移动如果 current_sum 小于 target说明需要增大三数之和应该将 left 指针右移如果 current_sum 大于 target说明需要减小三数之和应该将 right 指针左移如果 current_sum 等于 target那么这就是最完美的结果可以直接返回。提前终止条件与三数之和类似最接近三数之和也存在可以提前终止的情况。虽然不能像三数之和那样在 nums[i] 0 时直接 break因为 target 可能为负数但可以利用排序数组的特性进行优化。当三数之和已经非常接近目标值且继续遍历不可能得到更接近的结果时可以考虑提前终止。不过这种优化在实际实现中较为复杂通常不会使用。一个更实用的优化是当 left 和 right 指针相遇时说明当前 i 对应的所有可能三元组已经检查完毕可以继续下一个 i 的遍历。如果在某次遍历中找到了差值为零的结果即 current_sum target可以直接返回无需继续搜索。完整代码实现from typing import List class Solution: def threeSumClosest(self, nums: List[int], target: int) - int: n len(nums) if n 3: raise ValueError(数组长度至少为3) nums.sort() best_sum nums[0] nums[1] nums[2] best_diff abs(best_sum - target) for i in range(n - 2): if i 0 and nums[i] nums[i - 1]: continue left, right i 1, n - 1 while left right: current_sum nums[i] nums[left] nums[right] current_diff abs(current_sum - target) if current_diff best_diff: best_diff current_diff best_sum current_sum if current_sum target: left 1 elif current_sum target: right - 1 else: return current_sum return best_sum这段实现中包含了几个重要的优化细节。首先在外层循环中跳过与前一个元素相同的 nums[i]虽然本题不需要去重但这种优化可以避免对相同的第一个数进行重复搜索从而略微提升性能。其次在找到精确等于 target 的三数之和时立即返回这是最接近目标的完美情况不可能存在更优解。最后使用 best_diff 来记录当前的最小差值每次比较后更新最优结果。算法复杂度分析时间复杂度最接近三数之和问题的时间复杂度为 O(n²)其中 n 是数组长度。外层循环遍历 n-2 次内层双指针搜索在每次外层循环中最多移动 O(n) 次因此总时间复杂度为 O(n²)。排序操作的时间复杂度 O(n log n) 在大 O 表示法中被 O(n²) 吸收。与三数之和问题相比最接近三数之和不需要去重操作因此在某些情况下实际运行速度会更快一些。空间复杂度算法的空间复杂度为 O(1)只使用了常数个额外变量来存储指针位置、中间结果和最优解等。返回结果一个整数所占用的空间不计入空间复杂度的计算。这种常数级别的空间复杂度使得算法可以在内存受限的环境中使用。边界情况处理数组长度不足当数组长度小于 3 时无法组成三元组应该抛出异常或返回特定值。在实际面试中最好在函数开始时检查数组长度如果长度不足则直接返回合适的值或抛出有意义的异常。最小合法输入长度是 3此时唯一的三元组就是整个数组。重复元素的处理虽然本题不需要像三数之和那样进行严格的去重但处理重复元素仍然有其意义。当数组中包含大量重复元素时跳过与前一个相同的元素可以减少不必要的搜索。例如如果数组为 [-1, -1, -1, 2]以第一个 -1 作为第一个数搜索时已经检查了所有可能后续以第二个、第三个 -1 作为第一个数时会产生完全相同的搜索结果。特殊数值处理本题需要处理整数的各种特殊值情况包括负数、零、正数以及可能的整数溢出。当数组元素或 target 值较大时三数之和可能超出整型的表示范围。在 Python 中整数类型可以自动扩展因此不存在溢出问题但在 Java 或 C 等语言中需要注意使用 long 类型来存储可能超出 int 范围的结果。变种与扩展K数之和的最接近问题将问题扩展到 K 数之和K 3的最接近问题是自然而然的思路。基本思想是递归地固定前 K-2 个数然后在最后两个数上使用双指针。例如四数之和的最接近问题可以在 O(n³) 时间复杂度内解决。但随着 K 的增大时间复杂度会指数增长实际应用中需要权衡效率和需求。带权重的问题在实际应用中可能会遇到需要对不同位置的元素赋予不同权重的问题。例如给定权重数组 weights需要找到三个数使加权和最接近目标值。这种变种问题不能直接使用标准双指针法解决需要根据权重的性质选择其他算法或对原算法进行适当修改。找到所有最接近组合如果问题不仅要求最接近的三数之和还要求返回所有达到该最接近程度的三元组就需要在找到更优解时清空结果集并在找到同样优的解时添加到结果集中。这种变种问题在实际应用中可能更有价值因为它提供了更多的选择余地。测试用例设计为了全面验证算法的正确性需要设计多种类型的测试用例。首先是基本测试用例使用简单的数组和目标值验证算法的基本功能。其次是包含重复元素的测试用例验证算法在重复元素较多时仍能正确工作。再次是负数和正数混合的测试用例确保算法正确处理各种符号的数值。还有极端值测试用例使用最大值、最小值和边界值来验证算法的数值稳定性。最后是目标值在数组范围之外的测试用例此时最接近的三数之和应该是数组中三个最小或最大数之和。def test_three_sum_closest(): solution Solution() assert solution.threeSumClosest([-1, 2, 1, -4], 1) 2 assert solution.threeSumClosest([0, 0, 0], 1) 0 assert solution.threeSumClosest([1, 1, 1, 0], -100) 2 assert solution.threeSumClosest([1, 2, 5, 10, 11], 12) 13 assert solution.threeSumClosest([-1, -1, -1, 2, 2, 2], 0) 0 print(所有测试用例通过)总结最接近三数之和问题是三数之和问题的自然延伸它展示了双指针法在处理最接近类型问题时的灵活性。通过对数组进行排序并使用双指针遍历可以在 O(n²) 时间复杂度内找到最接近目标值的三数之和。虽然问题看似简单但在实现过程中需要注意指针移动策略、边界情况处理以及特殊值的正确性。通过本文的详细分析希望读者能够深入理解双指针法解决最接近问题的思路并将这种技巧应用到更多类似的算法问题中。最接近三数之和虽然是中等难度的问题但它涉及的算法思想和实现细节对于提升编程能力和应对面试都具有重要价值。
LeetCode 16：最接近三数之和 | 双指针法的灵活应用
发布时间：2026/5/22 2:01:26
LeetCode 16最接近三数之和 | 双指针法的灵活应用引言在算法面试中最接近三数之和3Sum Closest是三数之和问题的自然延伸编号为 LeetCode 16。这道题要求在一个整数数组中找出三个数使它们的和最接近给定的目标值。与三数之和不同这里不需要精确等于目标值而是寻找最接近的组合。这种问题的实用性很强例如在数据分析中寻找最接近某个目标值的组合或者在资源分配中寻找最优搭配等场景都可能出现类似的需求。最接近三数之和问题在思路上与三数之和非常相似都采用双指针法进行求解但在具体实现上存在一些关键区别。由于不需要精确匹配算法在找到接近的组合时不需要立即停止而是继续搜索直到遍历完所有可能的情况。同时由于不需要去重代码实现反而会更加简洁一些。本文将详细分析这一问题的解决思路和实现细节。问题分析题目描述给定一个长度为 n 的整数数组 nums 和一个目标值 target从 nums 中选择三个整数 nums[i]、nums[j]、nums[k]使得 (nums[i] nums[j] nums[k]) 与 target 之间的绝对差值最小。返回这三个数的和。例如输入 nums [-1, 2, 1, -4] 和 target 1最接近的三数之和为 2因为 -1 2 1 2与 1 的差值为 1。问题特点最接近三数之和问题的核心挑战在于如何在众多可能的三元组中快速找到最接近目标值的那一个。如果采用暴力枚举所有三元组的方式时间复杂度为 O(n³)对于大规模数据显然不够高效。更重要的是由于不需要精确匹配我们无法使用哈希表等数据结构来加速查找因为哈希表通常只适用于精确匹配的场景。双指针法再次成为解决这个问题的关键技巧。排序数组后通过左右指针的动态调整可以在 O(n²) 时间复杂度内遍历所有可能的三元组。与三数之和不同的是这里不需要进行去重处理因为我们的目标是找到最接近的三数之和而不是返回所有满足条件的不重复三元组。与三数之和的对比虽然最接近三数之和和三数之和都使用双指针法解决但两者在具体实现上存在几个重要区别。首先三数之和要求精确等于零而最接近三数之和只需要接近目标值这意味着后者不需要进行复杂的去重操作。其次在指针移动策略上三数之和在找到精确匹配后仍需要继续移动指针寻找其他组合但最接近三数之和在每次比较后都需要根据当前三数之和与目标值的关系来决定指针的移动方向。从返回值来看三数之和返回一个三元组列表而最接近三数之和返回一个整数三个数的和。这个差异也影响了两道题在代码实现上的细节处理。三数之和需要记录所有满足条件的组合而最接近三数之和只需要记录当前最优的组合。算法设计排序与初始化与三数之和一样解决最接近三数之和的第一步是对数组进行排序。排序不仅为双指针的移动提供了方向性指导还能使后续的遍历过程更加高效。排序后相同或相近的元素聚集在一起这虽然对本题的去重没有直接帮助因为不需要去重但保证了双指针移动逻辑的正确性。在开始遍历之前我们需要设置初始的最优结果。一种常见的选择是将数组中最前面的三个数之和作为初始最优值。但更稳妥的做法是初始化一个很大的差值例如无穷大然后在遍历过程中不断更新。初始化时直接将 best_sum 设置为前三数之和是可以接受的因为后续一定会找到更优或相等的结果。双指针遍历外层循环遍历数组的每个元素作为三元组的第一个数内层使用双指针在剩余范围内寻找最接近 target - nums[i] 的两个数。指针初始化时left 指向 i1right 指向数组末尾。每次计算当前三数之和 current_sum nums[i] nums[left] nums[right]然后计算与目标值的差值 diff abs(current_sum - target)。根据 diff 的大小更新最优结果如果当前差值小于历史最小差值则用当前三数之和更新 best_sum。接下来根据 current_sum 与 target 的关系决定指针的移动如果 current_sum 小于 target说明需要增大三数之和应该将 left 指针右移如果 current_sum 大于 target说明需要减小三数之和应该将 right 指针左移如果 current_sum 等于 target那么这就是最完美的结果可以直接返回。提前终止条件与三数之和类似最接近三数之和也存在可以提前终止的情况。虽然不能像三数之和那样在 nums[i] 0 时直接 break因为 target 可能为负数但可以利用排序数组的特性进行优化。当三数之和已经非常接近目标值且继续遍历不可能得到更接近的结果时可以考虑提前终止。不过这种优化在实际实现中较为复杂通常不会使用。一个更实用的优化是当 left 和 right 指针相遇时说明当前 i 对应的所有可能三元组已经检查完毕可以继续下一个 i 的遍历。如果在某次遍历中找到了差值为零的结果即 current_sum target可以直接返回无需继续搜索。完整代码实现from typing import List class Solution: def threeSumClosest(self, nums: List[int], target: int) - int: n len(nums) if n 3: raise ValueError(数组长度至少为3) nums.sort() best_sum nums[0] nums[1] nums[2] best_diff abs(best_sum - target) for i in range(n - 2): if i 0 and nums[i] nums[i - 1]: continue left, right i 1, n - 1 while left right: current_sum nums[i] nums[left] nums[right] current_diff abs(current_sum - target) if current_diff best_diff: best_diff current_diff best_sum current_sum if current_sum target: left 1 elif current_sum target: right - 1 else: return current_sum return best_sum这段实现中包含了几个重要的优化细节。首先在外层循环中跳过与前一个元素相同的 nums[i]虽然本题不需要去重但这种优化可以避免对相同的第一个数进行重复搜索从而略微提升性能。其次在找到精确等于 target 的三数之和时立即返回这是最接近目标的完美情况不可能存在更优解。最后使用 best_diff 来记录当前的最小差值每次比较后更新最优结果。算法复杂度分析时间复杂度最接近三数之和问题的时间复杂度为 O(n²)其中 n 是数组长度。外层循环遍历 n-2 次内层双指针搜索在每次外层循环中最多移动 O(n) 次因此总时间复杂度为 O(n²)。排序操作的时间复杂度 O(n log n) 在大 O 表示法中被 O(n²) 吸收。与三数之和问题相比最接近三数之和不需要去重操作因此在某些情况下实际运行速度会更快一些。空间复杂度算法的空间复杂度为 O(1)只使用了常数个额外变量来存储指针位置、中间结果和最优解等。返回结果一个整数所占用的空间不计入空间复杂度的计算。这种常数级别的空间复杂度使得算法可以在内存受限的环境中使用。边界情况处理数组长度不足当数组长度小于 3 时无法组成三元组应该抛出异常或返回特定值。在实际面试中最好在函数开始时检查数组长度如果长度不足则直接返回合适的值或抛出有意义的异常。最小合法输入长度是 3此时唯一的三元组就是整个数组。重复元素的处理虽然本题不需要像三数之和那样进行严格的去重但处理重复元素仍然有其意义。当数组中包含大量重复元素时跳过与前一个相同的元素可以减少不必要的搜索。例如如果数组为 [-1, -1, -1, 2]以第一个 -1 作为第一个数搜索时已经检查了所有可能后续以第二个、第三个 -1 作为第一个数时会产生完全相同的搜索结果。特殊数值处理本题需要处理整数的各种特殊值情况包括负数、零、正数以及可能的整数溢出。当数组元素或 target 值较大时三数之和可能超出整型的表示范围。在 Python 中整数类型可以自动扩展因此不存在溢出问题但在 Java 或 C 等语言中需要注意使用 long 类型来存储可能超出 int 范围的结果。变种与扩展K数之和的最接近问题将问题扩展到 K 数之和K 3的最接近问题是自然而然的思路。基本思想是递归地固定前 K-2 个数然后在最后两个数上使用双指针。例如四数之和的最接近问题可以在 O(n³) 时间复杂度内解决。但随着 K 的增大时间复杂度会指数增长实际应用中需要权衡效率和需求。带权重的问题在实际应用中可能会遇到需要对不同位置的元素赋予不同权重的问题。例如给定权重数组 weights需要找到三个数使加权和最接近目标值。这种变种问题不能直接使用标准双指针法解决需要根据权重的性质选择其他算法或对原算法进行适当修改。找到所有最接近组合如果问题不仅要求最接近的三数之和还要求返回所有达到该最接近程度的三元组就需要在找到更优解时清空结果集并在找到同样优的解时添加到结果集中。这种变种问题在实际应用中可能更有价值因为它提供了更多的选择余地。测试用例设计为了全面验证算法的正确性需要设计多种类型的测试用例。首先是基本测试用例使用简单的数组和目标值验证算法的基本功能。其次是包含重复元素的测试用例验证算法在重复元素较多时仍能正确工作。再次是负数和正数混合的测试用例确保算法正确处理各种符号的数值。还有极端值测试用例使用最大值、最小值和边界值来验证算法的数值稳定性。最后是目标值在数组范围之外的测试用例此时最接近的三数之和应该是数组中三个最小或最大数之和。def test_three_sum_closest(): solution Solution() assert solution.threeSumClosest([-1, 2, 1, -4], 1) 2 assert solution.threeSumClosest([0, 0, 0], 1) 0 assert solution.threeSumClosest([1, 1, 1, 0], -100) 2 assert solution.threeSumClosest([1, 2, 5, 10, 11], 12) 13 assert solution.threeSumClosest([-1, -1, -1, 2, 2, 2], 0) 0 print(所有测试用例通过)总结最接近三数之和问题是三数之和问题的自然延伸它展示了双指针法在处理最接近类型问题时的灵活性。通过对数组进行排序并使用双指针遍历可以在 O(n²) 时间复杂度内找到最接近目标值的三数之和。虽然问题看似简单但在实现过程中需要注意指针移动策略、边界情况处理以及特殊值的正确性。通过本文的详细分析希望读者能够深入理解双指针法解决最接近问题的思路并将这种技巧应用到更多类似的算法问题中。最接近三数之和虽然是中等难度的问题但它涉及的算法思想和实现细节对于提升编程能力和应对面试都具有重要价值。
