首页 > 其他分享 >最接近的三数之和

最接近的三数之和

时间:2023-04-16 23:11:53浏览次数:47  
标签:target nums int 三数 j0 枚举 接近 指针

最接近的三数之和

题目描述

image

题解

暴力解法即是三重循环,时间复杂度为\(O(n^3)\)。但是,这种多个数字求和的题目都可以通过双指针的方法降低一层循环。首先我们枚举元素a,那么对于剩下的两个元素bc,我们希望它们的和能够接近target-a。但是若要利用双指针,则需要一点预处理过程,即对数组升序排列,之后操作如下:image
利用\(p_b\) 和 \(p_c\) 来代表指向bc的指针,一开始,\(p_c\) 指向 $ n-1\(,即为右边界,\)p_b$指向 \(i + 1\) ,为左边界。image
另外,还可以做两个小优化:

  1. 当 \(a + b + c == target\) 时,我们可以直接返回。
  2. 当我们枚举 \(a,b,c\) 中任意元素并移动指针时,可以直接将其移动到下一个与这次枚举到的不相同的元素,减少枚举的次数。
    代码如下:
class Solution {
public:
    int threeSumClosest(vector<int>& nums, int target) {
        sort(nums.begin(), nums.end());
        int n = nums.size();
        int best = 1e7;

        // 根据差值的绝对值来更新答案
        auto update = [&](int cur) {
            if (abs(cur - target) < abs(best - target)) {
                best = cur;
            }
        };

        // 枚举 a
        for (int i = 0; i < n; ++i) {
            // 保证和上一次枚举的元素不相等
            if (i > 0 && nums[i] == nums[i - 1]) {
                continue;
            }
            // 使用双指针枚举 b 和 c
            int j = i + 1, k = n - 1;
            while (j < k) {
                int sum = nums[i] + nums[j] + nums[k];
                // 如果和为 target 直接返回答案
                if (sum == target) {
                    return target;
                }
                update(sum);
                if (sum > target) {
                    // 如果和大于 target,移动 c 对应的指针
                    int k0 = k - 1;
                    // 移动到下一个不相等的元素
                    while (j < k0 && nums[k0] == nums[k]) {
                        --k0;
                    }
                    k = k0;
                } else {
                    // 如果和小于 target,移动 b 对应的指针
                    int j0 = j + 1;
                    // 移动到下一个不相等的元素
                    while (j0 < k && nums[j0] == nums[j]) {
                        ++j0;
                    }
                    j = j0;
                }
            }
        }
        return best;
    }
};

标签:target,nums,int,三数,j0,枚举,接近,指针
From: https://www.cnblogs.com/parallel-138/p/17324386.html

相关文章

  • 哈希接近o1查找字符串
    P3538[POI2012]OKR-AHorriblePoem/*把这个人的因子分成循环节的因子:循环次数的因子:把循环次数的因子除去,也就是循环节的因子了循环节肯定是由某些因子组成的把因子从小到大除一次就可以了如果能够除掉这个因子,那除掉就一定是最有的*/#include<bits/stdc++.h>usi......
  • 亚马逊机器人上岗,将淘汰接近99%现有仓库员工
    来自国外媒体报道称,为了提升效率,亚马逊一直在自家的货运仓库中尝试新技术,其中包括利用机器人扫描传送带上的货物,并在几秒钟后将货物包裹在为每件商品定制的快递箱子中。亚马逊正在研究将这两种机器投入到更多物流仓库中,以此来替代工人的工作:每台机器至少可以淘汰掉24名工人。通常这......
  • 基于大数据的人工神经网络高效发电预测系统 python源代码 提出了一种发电预测方案,该方
    基于大数据的人工神经网络高效发电预测系统python源代码,代码按照高水平文章复现,保证正确提出了一种发电预测方案,该方案能够以接近耗电量的速度预测所需的电量。该方案使用大数据分析来处理每个州在过去20年收集的电力管理数据。然后使用神经网络(NN)模型训练系统,根据收集的数......
  • 15.三数之和——学习笔记
    题目:给你一个整数数组nums,判断是否存在三元组[nums[i],nums[j],nums[k]]满足i!=j、i!=k且j!=k,同时还满足nums[i]+nums[j]+nums[k]==0。请你返回所有和为0且不重复的三元组。注意:答案中不可以包含重复的三元组。示例1:输入:nums=[-1,0,1,2,-1,-4]输......
  • 15. 三数之和
    题目链接:15.三数之和方法:排序+相向双指针解题思路由题意可知,排序不影响结果,非递减排序之后3数之和满足单调性,即\(x<x1\)||\(y<y1\)||\(z<z1\),\(f(x,y,z)<f(x1,y1,z1)\);现在枚举\(x\)下标\(0<=i<=n-2\),在\([x+1,n-1]\)中选择\(y\),\(z\)的下标......
  • #yyds干货盘点# LeetCode程序员面试金典:最接近的三数之和
    题目:给你一个长度为n的整数数组 nums 和一个目标值 target。请你从nums中选出三个整数,使它们的和与 target 最接近。返回这三个数的和。假定每组输入只存在恰好一个解。 示例1:输入:nums=[-1,2,1,-4],target=1输出:2解释:与target最接近的和是2(-1+2+1=2)......
  • #yyds干货盘点# LeetCode程序员面试金典:三数之和
    题目:给你一个整数数组nums,判断是否存在三元组[nums[i],nums[j],nums[k]]满足i!=j、i!=k且j!=k,同时还满足nums[i]+nums[j]+nums[k]==0。请你返回所有和为0且不重复的三元组。注意:答案中不可以包含重复的三元组。  示例1:输入:nums=[-1,0,1,2,-1,-4]输......
  • 【230402-6】从集合{2,4,5,6,7,8}中选三数,使三数和可被3整除,有多少种取法?
    ......
  • 代码随想录Day7-Leetcode454. 四数相加 II,383. 赎金信 ,15. 三数之和 ,18. 四数之和
    454.四数相加II这个第一时间没想出来怎么做的;后面看了题解才发现可以两两分组;绝了/***@param{number[]}nums1*@param{number[]}nums2*@param{number[......
  • LeetCode15. 三数之和
    题目描述:给你一个整数数组nums,判断是否存在三元组[nums[i],nums[j],nums[k]]满足i!=j、i!=k且j!=k,同时还满足nums[i]+nums[j]+nums[k]==0。请你......