16.最接近的三数之和：排序 + 双指针

【LetMeFly】16.最接近的三数之和：排序 + 双指针

力扣题目链接：https://leetcode.cn/problems/3sum-closest/

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

返回这三个数的和。

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

 

示例 1：

输入：nums = [-1,2,1,-4], target = 1
输出：2
解释：与 target 最接近的和是 2 (-1 + 2 + 1 = 2) 。

示例 2：

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

 

提示：

• 3 <= nums.length <= 1000
• -1000 <= nums[i] <= 1000
• -104 <= target <= 104

方法一：排序 + 双指针

这道题和昨天的每日一题0016. 最接近的三数之和几乎一样，昨天是寻找三个数之和为target的数，今天是找到三个数之和最接近target的数。

因此，我们只需要在移动指针lr时，更新一下最优解即可。这里再次讲解一下大致思路：

第一层循环枚举数组中的每一个数nums[i]，对于一个特定的nums[i]：

使用双指针lr，初始值$l=i+1,r=n-1$。计算$nums[i]+nums[l]+nums[r]$（记为$s$）：

• 若$s==target$：直接返回target
• 若$s < target$：则$l$右移，并更新答案的最优值
• 若$s > target$：则$r$左移，并更新答案的最优值

最终返回最优的答案即可。

• 时间复杂度$O(n^2)$，其中$n=len(nums)$。
• 空间复杂度$O(\log n)$，复杂度为排序所致。

AC代码

C++

class Solution {
public:
    int threeSumClosest(vector<int>& nums, int target) {
        int ans = nums[0] + nums[1] + nums[2];
        int n = nums.size();
        sort(nums.begin(), nums.end());
        for (int i = 0; i < n; i++) {
            int finding = target - nums[i];
            int l = i + 1, r = n - 1;
            while (l < r) {
                int diff = finding - nums[l] - nums[r];
                if (diff == 0) {
                    return target;
                }
                else if (diff > 0) {  // target > nums[i] + nums[l] + nums[r]
                    l++;
                }
                else {
                    r--;
                }
                if (abs(diff) < abs(ans - target)) {
                    ans = target - diff;
                }
            }
        }
        return ans;
    }
};

Python

# from typing import List

class Solution:
    def threeSumClosest(self, nums: List[int], target: int) -> int:
        ans = sum(nums[:3])
        n = len(nums)
        nums.sort()
        for i in range(n):
            finding = target - nums[i]
            l, r = i + 1, n - 1
            while l < r:
                diff = finding - nums[l] - nums[r]
                if diff == 0:
                    return target
                elif diff > 0:  # target > nums[i] + nums[l] + nums[r]
                    l += 1
                else:
                    r -= 1
                if abs(diff) < abs(ans - target):
                    ans = target - diff
        return ans

同步发文于CSDN，原创不易，转载请附上原文链接哦~
Tisfy：https://letmefly.blog.csdn.net/article/details/131631627