leetcode-16-最接近的三数之和(中等)

2021/7/17 23:39:36

本文主要是介绍leetcode-16-最接近的三数之和(中等),对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

16. 最接近的三数之和(中等)

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

示例:

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

思路:排序+双指针

借鉴15题中的双指针思路,本题中只需要确定一个最优的答案,然后将其返回即可。因此,本题不需要排除重复答案,也不需要找到所有的最优组合。

  • 排序: 先将给定 nums 排序,复杂度为 O(NlogN)
  • 双指针思路: 固定 3 个指针,最小数字的指针 k,双指针 i,j 分设在数组索引(k, len(nums))两端,通过双指针交替向中间移动,记录对于每个k、i、j的和 nums[k] + nums[i] + nums[j] == s 的大小与target的关系:
    • 设置变量c用来记录前面组合中,s与target的最小差值的数额
    • s==target时,k、i、j所对应的三个数的和与target最接近,target为最优解直接返回即可;
    • s>target时,判断s-target与c的大小关系,若更小,则需要更新res=sc=s-target.否则,无需更新。最后更新j--
    • s<target时,判断target-s与c的大小关系,若更小,则需要更新res=sc=target-s.否则,无需更新。最后更新i++

(1) C++

class Solution {
public:
    int threeSumClosest(vector<int>& nums, int target) {
        int m = nums.size();
        sort(nums.begin(),nums.end());
        int c = INT_MAX;
        int res = 0;
        if(m<3) return 0;
        for(int k=0;k<m-2;k++){
            int i=k+1 , j=m-1;
            while(i<j){
                int s =nums[k]+nums[i]+nums[j];
                if(s == target ){
                    return target;
                }
                else if(s > target){
                    if(s-target<c){
                        res = s;
                        c = s-target;
                    }
                    j--;
                }
                else{
                    if(target-s <c){
                        res = s;
                        c = target-s;
                    }
                    i++;
                }
                
            }
        }
        return res;
    }
};

(2) python

class Solution:
    def threeSumClosest(self, nums: List[int], target: int) -> int:
        res = 0
        c = inf
        m = len(nums)
        nums.sort()
        for k in range(m-2):
            i = k+1
            j = m-1
            while(i<j):
                s = nums[k]+nums[i]+nums[j]
                if s==target:
                    return target
                elif s > target:
                    if(s-target<c):
                        res = s
                        c = s-target
                    j-=1
                else:
                    if(target-s < c):
                        res = s
                        c = target -s
                    i+=1
        return res


这篇关于leetcode-16-最接近的三数之和(中等)的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!


扫一扫关注最新编程教程