Fork me on GitHub

16 - 最接近的三数之和

发表于 | 分类于

题目描述

审题：
看到题目的我，悄悄点开了旁边的相关话题，恩又有双指针，大概知道怎么做了hiahia＼＼\٩(‘ω’)و//／／
三数之和-传送门

方法[类似三数之和]

  1. 将数组排序；
  2. 第一层循环遍历元素；
  3. 第二层循环使用双指针向中间靠拢检查；
  4. 遇到更符合条件的更新结果。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution:
    def threeSumClosest(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: int
        """
        nums.sort()
        closest = nums[0] + nums[1] + nums[2]
        for i in range(len(nums)):
            j, k = i + 1, len(nums) - 1
            while j < k:
                value = nums[i] + nums[j] + nums[k]
                closest = value if abs(target - value) < abs(target - closest) else closest
                if value == target:
                    return target
                elif value > target:
                    k -= 1
                else:
                    j += 1
        return closest