16.3Sum Closest

题目

Given an integer array nums of length n and an integer target, find three integers in nums such that the sum is closest to target.

Return the sum of the three integers.

You may assume that each input would have exactly one solution.

 

Example 1:

Input: nums = [-1,2,1,-4], target = 1
Output: 2
Explanation: The sum that is closest to the target is 2. (-1 + 2 + 1 = 2).

Example 2:

Input: nums = [0,0,0], target = 1
Output: 0
Explanation: The sum that is closest to the target is 0. (0 + 0 + 0 = 0).

 

Constraints:

• 3 <= nums.length <= 500
• -1000 <= nums[i] <= 1000
• -104 <= target <= 104

Related Topics

数组

双指针

排序

👍 1734

👎 0

思路

1. 转换为排序数组
2. 双指针寻找值
3. 重复处理
   • 重复的i可以跳过
   • 重复的指针值无需跳过

解法

# leetcode submit region begin(Prohibit modification and deletion)
class Solution:
    def threeSumClosest(self, nums: List[int], target: int) -> int:
        size = len(nums)
        res = pow(10, 5) + 1
        if size == 3:
            return sum(nums)

        nums.sort()

        for i in range(size - 2):
            if i > 0 and nums[i] == nums[i - 1]:
                continue

            left = i + 1
            right = size - 1

            while left < right:
                temp = nums[i] + nums[left] + nums[right]

                if temp == target:
                    return temp
                elif temp > target:
                    right -= 1
                else:
                    left += 1

                res = temp if abs(temp - target) < abs(res - target) else res

                # 需要寻找相近值，不是唯一值，无需跳过重复值
                # while left < right and nums[left] == nums[left - 1]:
                #     left += 1
                # while left < right and right + 1 < size and nums[right] == nums[right + 1]:
                #     right -= 1

        return res
# leetcode submit region end(Prohibit modification and deletion)

复杂度分析

• 时间复杂度O(n²)
  • 两层嵌套复杂为 n²
  • 排序时间复杂度为 O(Nlog(N))
• 空间复杂度O(1)
  • 返回值不计入复杂度