LeetCode题目（Python实现）：最接近的三数之和

朱雀 2023-07-11 05:36 15阅读 0赞

### 文章目录 ###

*  题目
 *   *  自己的想法
     *   *  算法实现
         *  执行结果
         *  复杂度分析
     *  改进版
     *   *  算法实现
         *  执行结果
         *  复杂度分析
     *  小结

# 题目 #

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

**示例** :

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

## 自己的想法 ##

### 算法实现 ###

class Solution:
        def threeSumClosest(self, nums: List[int], target: int) -> int:
            n = len(nums)
            res = float('inf')
            if n <= 3:
                return sum(nums)
            nums.sort()
    
            for i in range(n):
                if i > 0 and nums[i] >= target:
                    return sumAll
                if i > 0 and nums[i] == nums[i - 1]:
                    continue
                L = i + 1
                R = n - 1
                while L < R:
                    cha = target - nums[L] - nums[R] - nums[i]
                    if cha == 0:
                        return nums[L] + nums[R] + nums[i]
                    else:
                        if abs(cha) < abs(res):
                            res = cha
                            sumAll = nums[L] + nums[R] + nums[i]
                        if cha < 0:
                            R -= 1
                        else:
                            L += 1
            return sumAll

### 执行结果 ###

**执行结果** : 通过  
**执行用时** : 88 ms, 在所有 Python3 提交中击败了95.60%的用户  
**内存消耗** : 13.4 MB, 在所有 Python3 提交中击败了24.32%的用户  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1NTU2NTk5_size_16_color_FFFFFF_t_70]

### 复杂度分析 ###

*  时间复杂度：O(n^2)
 *  空间复杂度：O(1)

## 改进版 ##

### 算法实现 ###

class Solution:
        def threeSumClosest(self, nums: List[int], target: int) -> int:
            # closest three sum
    
            # nums[j]+nums[k]总是j变大，而k需要变小来满足其条件
            # 考虑其穿过结果的时候，总是可以同时获得两侧的结果
            key = lambda x: abs(x - target)
            nums.sort()
            ans = float("inf")
            for i in range(len(nums) - 2):
                k = len(nums) - 1
                val = target - nums[i]
                if nums[i] + nums[i + 1] + nums[i + 2] >= target:  # 提前截断
                    ans = min(ans, nums[i] + nums[i + 1] + nums[i + 2], key=key)
                    break
                if nums[i] + nums[-1] + nums[-2] <= target:  # 提前截断
                    ans = min(ans, nums[i] + nums[-1] + nums[-2], key=key)
                    continue
                for j in range(i + 1, len(nums)):
                    while k > j and nums[k] + nums[j] >= val:
                        k -= 1
                    if k > j:
                        ans = min(ans, nums[i] + nums[j] + nums[k], key=key)
                    if k + 1 < len(nums):  # k+1是其满足nums[k]+nums[j]>=val的情况
                        ans = min(ans, nums[i] + nums[j] + nums[k + 1], key=key)
                if ans == target:  # 主要的截断方式
                    return ans
            return ans

### 执行结果 ###

![在这里插入图片描述][20200303231948606.png]

### 复杂度分析 ###

*  时间复杂度：O(n^2)
 *  空间复杂度：O(1)

## 小结 ##

这道题与上一道的题目很相似，稍加改进即可做出。

之后发现了更快的代码，学习了一下，其实是对算法的进一步**改进**：

1.  对算法进行改进：快速对双指针进行锁定，对两边值求和在分别与目标值比对。
2.  对特判进行改进。

改进后算法比原来提高了**百分之五十左右**，说明改进的作用还是很明显的。这提示我们做题应该是两个步骤：

*  第一步是做出可行的算法，
 *  第二步是改进算法，

**二者结合就可以打败百分之九九的人**。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1NTU2NTk5_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200303230211898.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1NTU2NTk5,size_16,color_FFFFFF,t_70
[20200303231948606.png]: https://img-blog.csdnimg.cn/20200303231948606.png