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

文章目錄

16. 最接近的三數之和
- 題目描述
- 示例 1：
- 示例 2：
- 提示：
- 解題思路
- - 算法分析
  - 問題本質分析
  - 排序+雙指針法詳解
  - 雙指針移動策略
  - 搜索過程可視化
  - 各種解法對比
  - 算法流程圖
  - 邊界情況處理
  - 時間復雜度分析
  - 空間復雜度分析
  - 關鍵優化點
  - 實際應用場景
  - 測試用例設計
  - 代碼實現要點
- 完整題解代碼

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題"三數之和"的變種，需要找到最接近而不是完全相等的組合。這是一個經典的數組搜索和優化問題。

算法分析

這道題的核心思想是排序+雙指針優化，主要解法包括：

排序+雙指針法：先排序，再使用雙指針尋找最接近的和（推薦）
優化版本：添加提前剪枝和重復元素跳過
二分查找法：固定兩個數，用二分查找找第三個數
暴力解法：三重循環枚舉所有可能
遞歸方法：使用回溯思想逐步選擇

問題本質分析

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(n2)]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_n2空間O_1]C --> H[時間O_n2空間O_1]D --> I[時間O_n2log_n空間O_1]E --> J[時間O_n3空間O_1]F --> K[時間O_n3空間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_n2]D --> G[O_n2]E --> H[快速排序]F --> I[雙指針優化]G --> J[最優解法]J --> K[無法進一步優化]

空間復雜度分析

關鍵優化點

實際應用場景

測試用例設計

代碼實現要點

排序策略：
- 先對數組排序，便于雙指針操作
- 排序后可以跳過重復元素
雙指針優化：
- 固定第一個數，用雙指針尋找另外兩個數
- 根據sum與target的關系移動指針
距離計算：
- 使用絕對值計算距離
- 實時更新最接近的和
剪枝優化：
- 跳過重復元素避免重復計算
- 找到完全相等時提前返回
邊界處理：
- 處理數組長度為3的特殊情況
- 確保所有邊界條件都有正確輸出

這個問題的關鍵在于理解雙指針的移動策略和掌握距離計算的優化方法，通過排序和雙指針技術，將時間復雜度從O(n3)優化到O(n2)，實現高效的最接近三數之和查找。特別是雙指針的移動邏輯，需要根據當前和與目標值的關系來決定移動方向。

完整題解代碼

package mainimport ("fmt""sort"
)// threeSumClosest 最接近的三數之和 - 排序+雙指針法
// 時間復雜度: O(n2)，其中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(n2)
// 空間復雜度: 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(n2 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(n3)
// 空間復雜度: 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(n3)
// 空間復雜度: 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)}
}