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

发布于：2025-08-20 ⋅ 阅读:(20) ⋅ 点赞:(0)

文章目录

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 TD
    A[最接近的三数之和] --> 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 --> N
    L --> N
    M --> N

排序+双指针法详解

flowchart TD
    A[输入数组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 --> D
    
    I -->|是| 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 --> O
    O -->|是| P[left++]
    O -->|否| Q{sum > target?}
    O -->|否| R[返回sum]
    
    Q -->|是| S[right--]
    Q -->|否| R
    
    P --> I
    S --> I
    R --> F

双指针移动策略

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

搜索过程可视化

graph TD
    A["输入: 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 TD
    A[解法对比] --> 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 --> Q
    N --> Q
    O --> Q
    P --> Q

算法流程图

flowchart TD
    A[开始] --> B[对数组排序]
    B --> C[初始化closestSum和minDiff]
    C --> D[i = 0]
    
    D --> E{i < len(nums)-2?}
    E -->|否| F[返回closestSum]
    E -->|是| G{跳过重复元素?}
    
    G -->|是| H[i++]
    H --> D
    
    G -->|否| I[left = i+1, right = len(nums)-1]
    I --> J{left < right?}
    
    J -->|否| K[i++]
    K --> D
    
    J -->|是| 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 --> J
    P --> J
    Q --> R[结束]

边界情况处理

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

时间复杂度分析

graph TD
    A[时间复杂度分析] --> 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[无法进一步优化]

空间复杂度分析
空间复杂度分析
额外空间使用
排序空间
最终空间复杂度
常数空间
原地排序O_1
O_1
只使用局部变量
空间效率最优

关键优化点
优化策略
排序优化
双指针优化
剪枝优化
减少搜索空间
线性时间搜索
提前返回
跳过重复元素

实际应用场景
应用场景
数值逼近
优化问题
机器学习
金融计算
函数逼近
资源分配优化
参数调优
投资组合优化
核心算法组件

测试用例设计
测试用例
基础功能
边界情况
特殊情况
正常数组
有重复元素
负数数组
最小长度数组
最大长度数组
极值目标
完全相等
接近但不相等
所有元素相同
验证正确性
验证特殊情况

代码实现要点

  1. 排序策略：

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

  2. 双指针优化：

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

  3. 距离计算：

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

  4. 剪枝优化：

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

  5. 边界处理：

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

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

完整题解代码

package main

import (
	"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 + 1
		right := len(nums) - 1

		for left < right {
			sum := nums[i] + nums[left] + nums[right]
			diff := abs(sum - target)

			// 更新最接近的和
			if diff < minDiff {
				minDiff = diff
				closestSum = 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 + 1
		right := 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 = diff
				closestSum = 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 + 1
			right := len(nums) - 1

			// 二分查找最接近remaining的数
			for left <= right {
				mid := left + (right-left)/2
				sum := nums[i] + nums[j] + nums[mid]
				diff := abs(sum - target)

				if diff < minDiff {
					minDiff = diff
					closestSum = 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 = diff
					closestSum = 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 = diff
				closestSum = 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() {
	// 测试用例1
	nums1 := []int{-1, 2, 1, -4}
	target1 := 1
	result1 := 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()

	// 测试用例2
	nums2 := []int{0, 0, 0}
	target2 := 1
	result2 := 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 := -100
	result3 := 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   []int
		target 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)
	}
}

网站公告

今日签到

点亮在社区的每一天
去签到

热门文章

最新发布