16. 3Sum Closest

在一个数组中找到三个数的和，要求这个和与一个给定的数是最接近的

思路： 与3sum类似，只是每次不是与0做比较而是与目标数字做比较

Python:

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
class Solution:
    def threeSumClosest(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: int
        """
        # 5 star, 
        nums.sort()
        rs = nums[0] + nums[1] + nums[2]
        for i in range(len(nums) - 2):
            if i == 0 or nums[i] > nums[i-1]:
                left = i + 1
                right = len(nums) - 1
                while left < right:
                    total = nums[i] + nums[left] + nums[right]
                    if abs(target - total) < abs(target - rs):
                        rs = total
                    if total < target:
                        left += 1
                    elif total > target:
                        right -= 1
                    else:
                        return total
        return rs

Go:

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
func threeSumClosest(nums []int, target int) int {
	sort.Ints(nums)
	length := len(nums)
	gap := nums[0] + nums[1] + nums[2]
	for index, _ := range nums {
		if index == 0 || nums[index] > nums[index-1] {
			left, right := index+1, length-1
			for left < right {
				curSum := nums[index] + nums[right] + nums[left]
				if math.Abs(float64(curSum-target)) < math.Abs(float64(gap-target)) {
					gap = curSum
				}
				if curSum > target {
					right -= 1
				} else if curSum < target {
					left += 1
				} else {
					return curSum
				}
			}
		}

	}
	return gap

}