旭的小窝

16. 3Sum Closest

 
  • 2023年 06月08日

Promble

link: https://leetcode.com/problems/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.

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

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

Approach

九章算法 https://www.jiuzhang.com/solution/3sum-closest

Thought

  1. 首先需要对nums进行排序
  2. 需要一个暂存位置 ans = None
  3. 循环遍历nums，先确定一个位置i
  4. 定义双指针，left, right = i+1, len(nums) - 1
  5. 判断left < right
    1. 计算sum = nums[left] + nums[right] + nums[i]
    2. 如果 abs(sum - target) < abs(ans - target)
      1. ans = sum (用ans记录最小的和，返回这个值)
    3. 如果 sum <= target: left+=1
    4. 如果 sum > target： right-=1
  6. 返回ans

Code

class Solution:
    def threeSumClosest(self, nums: List[int], target: int) -> int:
        
        nums.sort()
        ans = None 

        for i in range(len(nums)):
            left, right = i+1, len(nums)-1
            while left < right:
                sum = nums[left] + nums[right] + nums[i]

                if sum == target:
                    return sum

                if ans is None or abs(sum-target) < abs(ans-target):
                    ans = sum

                if sum <= target:
                    left += 1
                else:
                    right -= 1

        return ans

Complexity

时间复杂度

  • 数组排序 $O(nlogn)$
  • 遍历过程，固定值为n次，双指针为n次，时间复杂度为$O(n^2)$
  • 总时间复杂度 $O(nlogn)+O(n^2)=O(n^2)$

空间复杂度 $O(1)$，只需要常量空间

搜索