【LeetCode】16. 最接近的三数之和

16. 最接近的三数之和

题目描述

给你一个长度为 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
解释：与 target 最接近的和是 0（0 + 0 + 0 = 0）。

提示：

• 3 <= nums.length <= 1000
• -1000 <= nums[i] <= 1000
• -10^4 <= target <= 10^4

解题思路

这道题要求从数组中找出三个数，使它们的和与目标值最接近。这是第15题"三数之和"的变种，需要找到最接近而不是完全相等的组合。这是一个经典的数组搜索和优化问题。

算法分析

这道题的核心思想是排序+双指针优化，主要解法包括：

1. 排序+双指针法：先排序，再使用双指针寻找最接近的和（推荐）
2. 优化版本：添加提前剪枝和重复元素跳过
3. 二分查找法：固定两个数，用二分查找找第三个数
4. 暴力解法：三重循环枚举所有可能
5. 递归方法：使用回溯思想逐步选择

问题本质分析

graph TDA[最接近的三数之和] --> B[数组排序]B --> C[固定第一个数]C --> D[双指针寻找]D --> E[更新最接近值]B --> F[时间复杂度优化]C --> G[减少搜索空间]D --> H[线性时间搜索]E --> I[绝对值比较]F --> J[排序O(n log n)]G --> K[跳过重复元素]H --> L[双指针O(n)]I --> M[距离计算]J --> N[总体复杂度O(n²)]K --> NL --> NM --> N

排序+双指针法详解

flowchart TDA[输入数组nums和目标值target] --> B[对数组排序]B --> C[初始化closestSum和minDiff]C --> D[固定第一个数i]D --> E{i < len(nums)-2?}E -->|否| F[返回closestSum]E -->|是| G[跳过重复元素]G --> H[设置双指针left=i+1, right=len(nums)-1]H --> I{left < right?}I -->|否| J[i++]J --> DI -->|是| K[计算sum = nums[i] + nums[left] + nums[right]]K --> L[计算diff = abs(sum - target)]L --> M{diff < minDiff?}M -->|是| N[更新minDiff和closestSum]M -->|否| O{sum < target?}N --> OO -->|是| P[left++]O -->|否| Q{sum > target?}O -->|否| R[返回sum]Q -->|是| S[right--]Q -->|否| RP --> IS --> IR --> F

双指针移动策略

graph TDA["当前和sum与target比较"] --> B{sum < target?}B -->|是| C[left指针右移]B -->|否| D{sum > target?}B -->|否| E[找到完全相等，直接返回]D -->|是| F[right指针左移]D -->|否| EC --> G[增大sum值]F --> H[减小sum值]G --> I[接近target]H --> II --> J[继续搜索更优解]E --> K[最优解找到]

搜索过程可视化

graph TDA["输入: nums = [-4, -1, 1, 2], target = 1"] --> B[排序后: [-4, -1, 1, 2]]B --> C["第1轮: i=0, nums[i]=-4"]C --> D["left=1, right=3, sum=-4+(-1)+2=-3"]D --> E["diff=|-3-1|=4, 更新closestSum=-3"]E --> F["sum < target, left++"]F --> G["left=2, right=3, sum=-4+1+2=-1"]G --> H["diff=|-1-1|=2, 更新closestSum=-1"]H --> I["sum < target, left++"]I --> J["left=3, right=3, 结束第1轮"]J --> K["第2轮: i=1, nums[i]=-1"]K --> L["left=2, right=3, sum=-1+1+2=2"]L --> M["diff=|2-1|=1, 更新closestSum=2"]M --> N["sum > target, right--"]N --> O["left=2, right=2, 结束第2轮"]O --> P["最终结果: 2"]

各种解法对比

graph TDA[解法对比] --> B[排序+双指针]A --> C[优化版本]A --> D[二分查找]A --> E[暴力解法]A --> F[递归方法]B --> G[时间O_n²空间O_1]C --> H[时间O_n²空间O_1]D --> I[时间O_n²log_n空间O_1]E --> J[时间O_n³空间O_1]F --> K[时间O_n³空间O_n]B --> L[推荐解法]C --> M[性能最优]D --> N[二分优化]E --> O[基础解法]F --> P[回溯思想]L --> Q[平衡性能和可读性]M --> QN --> QO --> QP --> Q

算法流程图

flowchart TDA[开始] --> B[对数组排序]B --> C[初始化closestSum和minDiff]C --> D[i = 0]D --> E{i < len(nums)-2?}E -->|否| F[返回closestSum]E -->|是| G{跳过重复元素?}G -->|是| H[i++]H --> DG -->|否| I[left = i+1, right = len(nums)-1]I --> J{left < right?}J -->|否| K[i++]K --> DJ -->|是| L[计算sum和diff]L --> M{更新最接近值}M --> N{sum与target比较}N -->|sum < target| O[left++]N -->|sum > target| P[right--]N -->|sum == target| Q[返回sum]O --> JP --> JQ --> R[结束]

边界情况处理

graph TDA[边界情况] --> B[数组长度=3]A --> C[重复元素]A --> D[负数情况]A --> E[目标值超出范围]B --> F[直接返回三数之和]C --> G[跳过重复元素避免重复计算]D --> H[正常处理，注意绝对值计算]E --> I[仍然能找到最接近值]F --> J[特殊情况处理]G --> JH --> JI --> J

时间复杂度分析

graph TDA[时间复杂度分析] --> B[排序阶段]B --> C[搜索阶段]C --> D[总体复杂度]B --> E[O_n log n]C --> F[O_n²]D --> G[O_n²]E --> H[快速排序]F --> I[双指针优化]G --> J[最优解法]J --> K[无法进一步优化]

空间复杂度分析

关键优化点

实际应用场景

测试用例设计

代码实现要点

1. 排序策略：

   • 先对数组排序，便于双指针操作
   • 排序后可以跳过重复元素

2. 双指针优化：

   • 固定第一个数，用双指针寻找另外两个数
   • 根据sum与target的关系移动指针

3. 距离计算：

   • 使用绝对值计算距离
   • 实时更新最接近的和

4. 剪枝优化：

   • 跳过重复元素避免重复计算
   • 找到完全相等时提前返回

5. 边界处理：

   • 处理数组长度为3的特殊情况
   • 确保所有边界条件都有正确输出

这个问题的关键在于理解双指针的移动策略和掌握距离计算的优化方法，通过排序和双指针技术，将时间复杂度从O(n³)优化到O(n²)，实现高效的最接近三数之和查找。特别是双指针的移动逻辑，需要根据当前和与目标值的关系来决定移动方向。

完整题解代码

package mainimport ("fmt""sort"
)// threeSumClosest 最接近的三数之和 - 排序+双指针法
// 时间复杂度: O(n²)，其中n是数组长度
// 空间复杂度: O(1)
func threeSumClosest(nums []int, target int) int {// 先对数组排序sort.Ints(nums)closestSum := nums[0] + nums[1] + nums[2]minDiff := abs(closestSum - target)// 固定第一个数，使用双指针寻找另外两个数for i := 0; i < len(nums)-2; i++ {// 跳过重复元素if i > 0 && nums[i] == nums[i-1] {continue}left := i + 1right := len(nums) - 1for left < right {sum := nums[i] + nums[left] + nums[right]diff := abs(sum - target)// 更新最接近的和if diff < minDiff {minDiff = diffclosestSum = sum}// 根据sum与target的关系移动指针if sum < target {left++} else if sum > target {right--} else {// 找到完全相等的，直接返回return sum}}}return closestSum
}// threeSumClosestOptimized 优化版本 - 提前剪枝
// 时间复杂度: O(n²)
// 空间复杂度: O(1)
func threeSumClosestOptimized(nums []int, target int) int {sort.Ints(nums)closestSum := nums[0] + nums[1] + nums[2]minDiff := abs(closestSum - target)for i := 0; i < len(nums)-2; i++ {// 跳过重复元素if i > 0 && nums[i] == nums[i-1] {continue}left := i + 1right := len(nums) - 1// 提前剪枝：如果当前最小值已经为0，直接返回if minDiff == 0 {return closestSum}for left < right {sum := nums[i] + nums[left] + nums[right]diff := abs(sum - target)if diff < minDiff {minDiff = diffclosestSum = sum}if sum < target {left++// 跳过重复元素for left < right && nums[left] == nums[left-1] {left++}} else if sum > target {right--// 跳过重复元素for left < right && nums[right] == nums[right+1] {right--}} else {return sum}}}return closestSum
}// threeSumClosestBinarySearch 二分查找版本
// 时间复杂度: O(n² log n)
// 空间复杂度: O(1)
func threeSumClosestBinarySearch(nums []int, target int) int {sort.Ints(nums)closestSum := nums[0] + nums[1] + nums[2]minDiff := abs(closestSum - target)for i := 0; i < len(nums)-2; i++ {for j := i + 1; j < len(nums)-1; j++ {// 使用二分查找寻找第三个数remaining := target - nums[i] - nums[j]left := j + 1right := len(nums) - 1// 二分查找最接近remaining的数for left <= right {mid := left + (right-left)/2sum := nums[i] + nums[j] + nums[mid]diff := abs(sum - target)if diff < minDiff {minDiff = diffclosestSum = sum}if nums[mid] < remaining {left = mid + 1} else if nums[mid] > remaining {right = mid - 1} else {return sum}}}}return closestSum
}// threeSumClosestBruteForce 暴力解法 - 三重循环
// 时间复杂度: O(n³)
// 空间复杂度: O(1)
func threeSumClosestBruteForce(nums []int, target int) int {closestSum := nums[0] + nums[1] + nums[2]minDiff := abs(closestSum - target)for i := 0; i < len(nums)-2; i++ {for j := i + 1; j < len(nums)-1; j++ {for k := j + 1; k < len(nums); k++ {sum := nums[i] + nums[j] + nums[k]diff := abs(sum - target)if diff < minDiff {minDiff = diffclosestSum = sum}}}}return closestSum
}// threeSumClosestRecursive 递归方法 - 回溯思想
// 时间复杂度: O(n³)
// 空间复杂度: O(n)，递归调用栈
func threeSumClosestRecursive(nums []int, target int) int {closestSum := nums[0] + nums[1] + nums[2]minDiff := abs(closestSum - target)var backtrack func(index, count, currentSum int)backtrack = func(index, count, currentSum int) {if count == 3 {diff := abs(currentSum - target)if diff < minDiff {minDiff = diffclosestSum = currentSum}return}if index >= len(nums) {return}// 选择当前数backtrack(index+1, count+1, currentSum+nums[index])// 不选择当前数backtrack(index+1, count, currentSum)}backtrack(0, 0, 0)return closestSum
}// abs 计算绝对值
func abs(x int) int {if x < 0 {return -x}return x
}func main() {// 测试用例1nums1 := []int{-1, 2, 1, -4}target1 := 1result1 := threeSumClosest(nums1, target1)fmt.Printf("示例1: nums = %v, target = %d\n", nums1, target1)fmt.Printf("输出: %d\n", result1)fmt.Printf("期望: 2\n")fmt.Printf("结果: %t\n", result1 == 2)fmt.Println()// 测试用例2nums2 := []int{0, 0, 0}target2 := 1result2 := threeSumClosest(nums2, target2)fmt.Printf("示例2: nums = %v, target = %d\n", nums2, target2)fmt.Printf("输出: %d\n", result2)fmt.Printf("期望: 0\n")fmt.Printf("结果: %t\n", result2 == 0)fmt.Println()// 额外测试用例nums3 := []int{1, 1, 1, 0}target3 := -100result3 := threeSumClosest(nums3, target3)fmt.Printf("额外测试: nums = %v, target = %d\n", nums3, target3)fmt.Printf("输出: %d\n", result3)fmt.Printf("期望: 2\n")fmt.Printf("结果: %t\n", result3 == 2)fmt.Println()// 测试优化版本fmt.Println("=== 优化版本测试 ===")result1Opt := threeSumClosestOptimized(nums1, target1)result2Opt := threeSumClosestOptimized(nums2, target2)fmt.Printf("优化版本示例1: %d\n", result1Opt)fmt.Printf("优化版本示例2: %d\n", result2Opt)fmt.Printf("结果一致: %t\n", result1Opt == result1 && result2Opt == result2)fmt.Println()// 测试二分查找版本fmt.Println("=== 二分查找版本测试 ===")result1Bin := threeSumClosestBinarySearch(nums1, target1)result2Bin := threeSumClosestBinarySearch(nums2, target2)fmt.Printf("二分查找版本示例1: %d\n", result1Bin)fmt.Printf("二分查找版本示例2: %d\n", result2Bin)fmt.Printf("结果一致: %t\n", result1Bin == result1 && result2Bin == result2)fmt.Println()// 测试暴力解法fmt.Println("=== 暴力解法测试 ===")result1BF := threeSumClosestBruteForce(nums1, target1)result2BF := threeSumClosestBruteForce(nums2, target2)fmt.Printf("暴力解法示例1: %d\n", result1BF)fmt.Printf("暴力解法示例2: %d\n", result2BF)fmt.Printf("结果一致: %t\n", result1BF == result1 && result2BF == result2)fmt.Println()// 测试递归方法fmt.Println("=== 递归方法测试 ===")result1Rec := threeSumClosestRecursive(nums1, target1)result2Rec := threeSumClosestRecursive(nums2, target2)fmt.Printf("递归方法示例1: %d\n", result1Rec)fmt.Printf("递归方法示例2: %d\n", result2Rec)fmt.Printf("结果一致: %t\n", result1Rec == result1 && result2Rec == result2)fmt.Println()// 边界值测试fmt.Println("=== 边界值测试 ===")boundaryTests := []struct {nums   []inttarget int}{{[]int{1, 1, 1}, 3},                 // 最小值{[]int{1000, 1000, 1000}, 3000},     // 最大值{[]int{-1000, -1000, -1000}, -3000}, // 负值{[]int{0, 0, 0}, 0},                 // 零值{[]int{1, 2, 3}, 6},                 // 完全相等{[]int{1, 2, 3}, 5},                 // 接近但不相等}for i, test := range boundaryTests {result := threeSumClosest(test.nums, test.target)fmt.Printf("测试%d: nums = %v, target = %d, result = %d\n", i+1, test.nums, test.target, result)}
}