LeetCode 16. 3Sum Closest 题解

LeetCode 16. 3Sum Closest 题解题目描述给你一个长度为n的整数数组nums和一个目标值target。请你从nums中选出三个整数使它们的和与target最接近。返回这三个数的和。注意假定每组输入只存在恰好一个解。示例 1输入nums [-1,2,1,-4], target 1 输出2 解释与 target 最接近的和是 2 (-1 2 1 2) 。示例 2输入nums [0,0,0], target 1 输出0解题思路方法排序 双指针思路首先对数组进行排序这样可以方便地使用双指针来查找初始化一个变量closest_sum来存储最接近目标值的和初始值为前三个元素的和遍历数组中的每个元素作为三元组的第一个元素使用双指针分别指向当前元素的下一个元素和数组的最后一个元素计算三个元素的和计算当前和与目标值的差值的绝对值如果当前差值的绝对值小于之前的最小差值更新closest_sum如果当前和小于目标值左指针右移如果当前和大于目标值右指针左移如果当前和等于目标值直接返回当前和复杂度分析时间复杂度O(n²)其中 n 是数组的长度。排序的时间复杂度是 O(n log n)遍历和双指针的时间复杂度是 O(n²)。空间复杂度O(1)只需要常数级的额外空间。代码实现方法排序 双指针class Solution: def threeSumClosest(self, nums: List[int], target: int) - int: n len(nums) # 排序 nums.sort() # 初始化最接近的和为前三个元素的和 closest_sum nums[0] nums[1] nums[2] for i in range(n - 2): # 双指针 left i 1 right n - 1 while left right: current_sum nums[i] nums[left] nums[right] # 计算当前和与目标值的差值的绝对值 current_diff abs(current_sum - target) # 计算之前最接近的和与目标值的差值的绝对值 closest_diff abs(closest_sum - target) # 如果当前差值更小更新最接近的和 if current_diff closest_diff: closest_sum current_sum # 根据当前和与目标值的关系移动指针 if current_sum target: left 1 elif current_sum target: right - 1 else: # 如果当前和等于目标值直接返回 return current_sum return closest_sum测试用例测试用例 1输入nums [-1,2,1,-4], target 1输出2测试用例 2输入nums [0,0,0], target 1输出0测试用例 3输入nums [1,1,1,0], target -100输出2测试用例 4输入nums [1,2,4,8,16,32,64,128], target 82输出82总结本题是三数之和问题的变种主要考察对排序和双指针技巧的理解和使用。通过排序和双指针我们可以有效地找到与目标值最接近的三数之和。排序的核心思想是将数组按照升序排列这样我们可以使用双指针来高效地查找和调整三数之和。双指针的核心思想是通过移动左指针和右指针我们可以根据当前和与目标值的关系来调整指针的位置从而找到最接近的和。这种方法不仅适用于最接近的三数之和问题还可以应用于许多其他需要查找最接近值的问题。掌握排序和双指针的使用对于解决这类问题非常重要。