[leetcode algorithms]題目16

16. 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.

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).

自己寫的代碼：

先定義一個二分查找函數binSearch，既可以查找升序又可以查找降序的數組。將數組排序，外層循環生成left, 內層循環生成mid，然後二分查找right，使得left + mid + right = target。如果left + mid + right大於target，且預期left + mid + right會越來越大，那麼循環可以提前終止了。運行時間1185 ms

class Solution: def binSearch(self, nums, target, low, high, descending): if descending: if target >= nums[low]: return nums[low] if target <= nums[high]: return nums[high] while low <= high: mid = (low + high) // 2 mid_val = nums[mid] if mid_val < target: high = mid - 1 elif mid_val > target: low = mid + 1 else: return mid_val else: if target <= nums[low]: return nums[low] if target >= nums[high]: return nums[high] while low <= high: mid = (low + high) // 2 mid_val = nums[mid] if mid_val < target: low = mid + 1 elif mid_val > target: high = mid - 1 else: return mid_val low_val = nums[low] high_val = nums[high] return min(low_val, high_val, key=lambda x: abs(x - target)) def threeSumClosest(self, nums, target): descending = (target < 0) nums = sorted(nums, reverse=descending) n = len(nums) key = float(inf) for i in range(n - 2): num1 = nums[i] for j in range(i + 1, n - 1): num2 = nums[j] num3 = self.binSearch(nums, target - num2 - num1, j + 1, n - 1, descending) tmp = abs(num1 + num2 + num3 - target) if tmp < key: key = tmp res = num1 + num2 + num3 if (num1 + num2) < target < 0 or (num1 + num2) > target > 0: break return res

推薦閱讀：