未分類

3Sum Closest

Array, Go, LeetCode, TwoPointers

3Sum Closest

Given an array S of n integers, find three integers in S such that the sum is closest to a given number, target. Return the sum of the three integers. You may assume that each input would have exactly one solution.

1
2
3
For example, given array S = {-1 2 1 -4}, and target = 1.
The sum that is closest to the target is 2. (-1 + 2 + 1 = 2).
提示 解題應用
Array Array/Slice
TwoPointers 記錄index位置

Default:

1
2
3
func threeSumClosest(nums []int, target int) int {
}

解答思路:

建議可以先參考前一篇3Sum的解法，解說較為詳細，基本上概念完全一樣，只是將先前題的程式碼做刪減及稍作修改而已，如果可以找出三個總合為0的所有組合，當然只是要找與目標值最接近的總合就更加容易。

要從一陣列中找出3個值總合與目標值最接近的總合，一樣先將整個陣列做排序，每取一個就從該元素後頭的陣列找另外兩個對應的所有組合，以左右兩邊開始找起，當最左與最右值再與前面取出的值相加大於目標時，表示總合太大將右側的index向前推一點找比較小的值並重新判斷，此時如果總合與目標值距離小於最小值就取代並紀錄此次總合，又當總合小於目標時表示太小，將左側的index向後推一點找比較大的值並再次判斷，同樣的如果距離小於最小值就取代並紀錄總合，最後如果找到剛好等於目標值的情況就直接回傳總合，否則如果到遍歷結束都沒有相等的結果則回傳最小值。

程式碼解說:

對照前一題的程式碼，主要只有修改從後頭的陣列找另外兩個對應所有組合的部分，首先是原本總合要與0相等及與0比較大小的部分都改為目標值target，接著是如果總合與目標值相等，此時就不必再找其它可能，因為肯定與目標值最近，直接回傳總合即可，而如果是總合大於目標值或小於目標值的情況，此時要再判斷總合與目標值的距離是否小於最小值，如果是就將距離取代最小值同時記錄此次的總合，最後如果一直都沒有與目標值相等的情況則回傳所記錄下距離最小的總合

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
front = i + 1
rear = len(nums) - 1
for front < rear {
	sum = v + nums[front] + nums[rear]
	if sum == target {
		return sum
	} else if sum > target {
		if sum-target < min {
			min = sum - target
			result = sum
		}
		rear--
	} else {
		if target-sum < min {
			min = target - sum
			result = sum
		}
		front++
	}
}

完整程式碼:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
func threeSumClosest(nums []int, target int) int {
	var sum int
	var front int
	var rear int
	var result int
	min := math.MaxInt32
	sort.Ints(nums)
	for i, v := range nums {
		if i > 0 && v == nums[i-1] {
			continue
		}
		front = i + 1
		rear = len(nums) - 1
		for front < rear {
			sum = v + nums[front] + nums[rear]
			if sum == target {
				return sum
			} else if sum > target {
				if sum-target < min {
					min = sum - target
					result = sum
				}
				rear--
			} else {
				if target-sum < min {
					min = target - sum
					result = sum
				}
				front++
			}
		}
	}
	return result
}

總結:

可以先參考前一篇3Sum的解法，解說較為詳細，基本上概念完全一樣。

要從一陣列中找出3個值總合與目標值最接近的總合，一樣先將整個陣列做排序，每取一個就從該元素後頭的陣列找另外兩個對應的所有組合，以左右兩邊開始找起，當最左與最右值再與前面取出的值相加大於目標時，表示總合太大將右側的index向前推一點找比較小的值並重新判斷，此時如果總合與目標值距離小於最小值就取代並紀錄此次總合，又當總合小於目標時表示太小，將左側的index向後推一點找比較大的值並再次判斷，同樣的如果距離小於最小值就取代並紀錄總合，最後如果找到剛好等於目標值的情況就直接回傳總合，否則如果到遍歷結束都沒有相等的結果則回傳最小值。

分享到