LeetCode 16. 最接近的三数之和（中）

类似第15题，不过把判断过程修改成求最小差值，而非等于某个数。

题目

给定一个包括 n 个整数的数组 nums 和 一个目标值 target。找出 nums 中的三个整数，使得它们的和与 target 最接近。返回这三个数的和。假定每组输入只存在唯一答案。

示例

1
2
例如，给定数组 nums = [-1，2，1，-4], 和 target = 1.
与 target 最接近的三个数的和为 2. (-1 + 2 + 1 = 2).

考察知识点

数组、双指针、排序

核心思想

类似第15题，不过把判断过程修改成求最小差值，而非等于某个数。

  • 本题目因为要计算三个数，如果靠暴力枚举的话时间复杂度会到\(O(n^3)\)，需要降低时间复杂度
  • 首先进行数组排序，时间复杂度 \(O(nlogn)\)
  • 在数组 nums 中，进行遍历，每遍历一个值利用其下标i，形成一个固定值 nums[i]
  • 再使用前指针指向 start = i + 1 处，后指针指向 end = len(nums) - 1 处，也就是结尾处。
  • 根据 sum = nums[i] + nums[start] + nums[end] 的结果，判断 sum 与目标 target 的距离，如果更近则更新结果 ans
  • 同时判断 sum 与 target 的大小关系，因为数组有序，如果 sum > target 则 end--，如果 sum < target 则 start++，如果 sum == target 则说明距离为 0 直接返回结果
  • 整个遍历过程，固定值为 n 次，双指针为 n 次，时间复杂度为 \(O(n^2)\)
  • 总时间复杂度：\(O(nlogn) + O(n^2) = O(n^2)\)

LeetCode题解

Python版本

根据思路手写的一个版本

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
class Solution:
    def threeSumClosest(self, nums: list, target: int) -> int:
        _len = len(nums)
        if(not nums or _len<3):
            return []
        nums.sort()
        ans = nums[0] + nums[1] + nums[2]

        for i in range(_len):
            L = i + 1  # 左指针
            R = _len - 1  # 右指针
            while(L<R):
                _sum = nums[i]+nums[L]+nums[R]
                if abs(target-_sum) < abs(target-ans):
                    ans = _sum
                if _sum > target:                    R -= 1

                elif _sum < target:
                    L += 1
                else:
                    return ans
        return ans


print("leet code accept!!!")
Input = [[-1, 2, 1, -4]]
Input1 = [1]
Answer = [2]

if __name__ == "__main__":
    solution = Solution()
    for i in range(len(Input)):
        print("-"*50)
        result = solution.threeSumClosest(Input[i], Input1[i])
        print(result)
        print(result==Answer[i])

时间复杂度\(O(n)\)