Skip to content

Latest commit

 

History

History
57 lines (42 loc) · 1.73 KB

最接近的三数之和.md

File metadata and controls

57 lines (42 loc) · 1.73 KB

最接近的三数之和

题目描述

给你一个长度为 n 的整数数组 nums 和一个目标值 target。请你从 nums 中选出三个整数,使它们的和与 target 最接近。

返回这三个数的和。

假定每组输入只存在恰好一个解。

示例

示例 1

输入nums = [-1,2,1,-4] target = 1

输出2

示例 2

输入nums = [0,0,0] target = 1

输出0

解题思路

  • 与三数之和一样,还是要固定一个数,然后双指针移动,只不过这次是求和最接近target的值,所以需要用绝对值来比较大小(ox3f并没有用绝对值的方法,但是绝对值我比较好理解,因为最接近表示的是距离,距离为非负值)。
  • 但同时还需要维护一个变量difference,用来记录最小的差值
    self.nums.sort()
    difference = float('inf')
  • 优化一,需要判断当前的变量i是不是重复的,如果是重复的,那么跳过这次循环
    if i > 0 and nums[i] == nums[i - 1]:
        continue
  • 优化二,如果当前最小的三个数比target大,且与target的差绝对值比difference大,那么后面的数肯定比target大,所以直接break
min_sum = self.nums[i] + self.nums[i + 1] + self.nums[i + 2]
    if min_sum > self.target and abs(min_sum - self.target) > difference:
        break
  • 优化三,如果当前最大的三个数比target小,且与target的差绝对值比difference大,那么后面的数肯定比target小,直接continue
max_sum = self.nums[-1] + self.nums[-2] + self.nums[-3]
    if max_sum < self.target and abs(max_sum - self.target) > difference:
        continue