首页 > 其他分享 > 15. 三数之和

15. 三数之和

时间:2023-04-07 22:26:33浏览次数:47  
标签:15 nums ++ 三数 sum -- ans size

题目链接: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\)的下标\(l\), \(r\),初始化\(l = x + 1,r = n - 1\);
    (1)若\(nums[i] > 0\),则后续没有\(f(x, y, z) == 0\);
    (2)若\(nums[i] == nums[i - 1]\),跳过此次循环,去除重复的数对,因为\(x = i,l = x + 1, r = n - 1\)的满足条件的三元组在\(x = i - 1, l = x + 1, r = n - 1\)中已经计算过了;
    (3)计算\(sum = f(x, y, z)\):
    • \(sum < 0\),由于\(r\)此时已经是最大值,故 \(l ++\);
    • \(sum > 0\),同上,\(r --\) ;
    • \(sum == 0\),将\({nums[i], nums[l], nums[r]}\)加入返回数组,此时若\(nums[l] == nums[l + 1]\),会出现重复数对,故 \(l ++\) ,直到\(nums[l] != nums[l + 1]\),对于右端点同理,若\(nums[r] == nums[r - 1]\),则 \(r --\) ,直到\(nums[r] != nums[r - 1]\)。

代码

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        vector<vector<int>> ans; 
        if (nums.size() < 3) return ans;
        sort(nums.begin(), nums.end());
        for (int i = 0; i < nums.size() - 2; i ++ ) {
            if (nums[i] > 0) return ans;
            if (i > 0 && nums[i] == nums[i - 1]) continue;
            int l = i + 1, r = nums.size() - 1;
            while (l < r) {
                int sum = nums[i] + nums[l] + nums[r];
                if (sum < 0) l ++ ;
                else if (sum > 0) r -- ;
                else {
                    ans.push_back({nums[i], nums[l], nums[r]});
                    while (l < r && nums[l] == nums[l + 1]) l ++ ; 
                    while (l < r && nums[r] == nums[r - 1]) r -- ;
                    l ++ ;
                    r -- ;
                }
            }
        }
        return ans;
    }
};

复杂度分析

时间复杂度:\(O(n^2)\);
空间复杂度:\(O(1)\)。

标签:15,nums,++,三数,sum,--,ans,size
From: https://www.cnblogs.com/lxycoding/p/17297511.html

相关文章

  • npm is known not to run on Node.js v8.15.0
    ########### >npminstall--legacy-peer-depsERROR:npmisknownnottorunonNode.jsv8.15.0You'llneedtoupgradetoanewerNode.jsversioninordertousethisversionofnpm.Youcanfindthelatestversionathttps://nodejs.org/ 删除:C......
  • L15_告诉别人自己想去的地方
    视频资料概述打车的时候,需要告诉司机去哪个地方时,可采用:地名+までお願いします的句式表达自己想要去某个地方,比如:くうこうまでお願いします想要去机场动画会话A:どちらまで您去哪儿?B:猿の温泉までお願いします麻烦你,去野猿温泉。A:はい、わかりました好......
  • 剑指 Offer 15. 二进制中1的个数
    题目链接:剑指Offer15.二进制中1的个数方法一:位运算解题思路x=n&-n,\(x\)表示\(n\)的最后一位\(1\)所对应的值,每减去一次\(x\),相当于有一个\(1\),\(res++\)。代码classSolution{public:inthammingWeight(uint32_tn){intres=0;w......
  • 【web 开发基础】PHP 的流程控制之嵌套(巢状)条件分支结构 -PHP 快速入门 (15)
    嵌套条件分支结构嵌套条件分支结构,也称为巢状条件分支结构。其实就是将if语句进行嵌套,即是在if或者else后面的语句块中又包含if语句。if语句可以无限层第嵌套在其他if语句中,这给程序的不同部分的条件执行提供了充分的弹性,是程序设计中经常使用的技术。其语法格式如下所示:if(表达式1......
  • hdu-1540(线段树+区间合并)
    TunnelWarfareHDU-1540思路:没被摧毁的村庄为1,否则为0,用len记录线段树维护区间的两个信息:前缀最长1的序列pre后缀最长1的序列suf父节点与左右子节点的关系://lc为左节点,rc为右节点1.若左右结点都不满1,则tr[p].pre=tr[lc].pre,tr[p].suf=tr[rc].suf2.若左节点满1,tr......
  • opencv-python 4.15. 基于分水岭算法的图像分割
    理论任何灰度图像都可以看作是地形表面,其中高强度表示峰和丘陵,而低强度表示山谷。你开始用不同颜色的水(标签)填充每个孤立的山谷(局部最小值)。随着水的上升,取决于附近的峰值(梯度),来自不同山谷的水,明显具有不同的颜色将开始融合。为避免这种情况,你需要在水合并的位置建立障碍。你继续......
  • 153. 寻找旋转排序数组中的最小值
    已知一个长度为n的数组,预先按照升序排列,经由1到n次旋转后,得到输入数组。例如,原数组nums=[0,1,2,4,5,6,7]在变化后可能得到:若旋转4次,则可以得到[4,5,6,7,0,1,2]若旋转7次,则可以得到[0,1,2,4,5,6,7]注意,数组[a[0],a[1],a[2],...,a[n-1]]旋转一次的结果为数......
  • docker-compose 部署 consul v1.15.2
    server1配置文件{"node_name":"consul-server1","datacenter":"zhongtai","domain":"consul","server":true,"log_level":"INFO","ui_conf......
  • HDU - 3715 Go Deeper (二分 + 2-SAT)
    题目大意:给出一个递归函数,问这个递归函数最多能递归几层解题思路:二分枚举递归层数,然后依此建边如果给出的c[i]为0时,那么x[a[i]]和x[b[i]]中的其中一个要为真,连边即为!a[i]->b[i],!b[i]->a[i]如果给出的c[i]为1时,那么x[a[i]]和x[b[i]]两个要么都为真,要么都为假,连边即为a[i]->b[i......
  • Qt5.15编译Oracle 19c驱动
     一、下载Oracle 19c驱动,需要下载两个包,注意分x86和x64x86下载地址:InstantClientforWindows32-bit(oracle.com) ① instantclient-basic-nt-19.18.0.0.0dbru.zip ② instantclient-sdk-nt-19.18.0.0.0dbru.zipx64下载地址:InstantClientforMicrosoftWindows(x......