leetcode: 3Sum
leetcode: 3Sum
- 1. 题目描述
- 2. 思考
- 3. 解题
- 3. 总结
1. 题目描述
Given an integer array nums, return all the triplets [nums[i], nums[j], nums[k]]
such that i != j, i != k, and j != k, and nums[i] + nums[j] + nums[k] == 0.
Notice that the solution set must not contain duplicate triplets.
Example1
Input: nums = [-1,0,1,2,-1,-4]
Output: [[-1,-1,2],[-1,0,1]]
Explanation:
nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0.
nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0.
nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0.
The distinct triplets are [-1,0,1] and [-1,-1,2].
Notice that the order of the output and the order of the triplets does not matter.
Example 2:
Input: nums = [0,1,1]
Output: []
Explanation: The only possible triplet does not sum up to 0.
Example 3:
Input: nums = [0,0,0]
Output: [[0,0,0]]
Explanation: The only possible triplet sums up to 0.
Constraints:
- 3 <= nums.length <= 3000
- 105 <= nums[i] <= 105
2. 思考
在做该题之前,建议对Two Sum和leetcode: Two Sum II - Input Array is Sorted,这两道题目先进行了解。
Two Sum问题的最优时间复杂度为o(n)o(n)o(n),因此对于3Sum问题应该来讲较容易的写出时间复杂度为o(n2)o(n^2)o(n2)的解法。但该题目的难点在于triplet要找出所有的方案,同时要去重。
首先,由于当前预设的时间复杂度为o(n2)o(n^2)o(n2),因此可以先对array进行排序,这样不会改变时间复杂度的量级,同时有利于下面的去重操作。
首先对于外层循环,我们仅对首次遇到的元素进行进一步的内层循环。如何理解这句话:

假如当前外层循环,进行到红色区域段。对于第一个-7, 可以将其之后的数组SSS进行内层循环,找出和为7的两个元素的所有不重复方案。找到的方案熟练假设为nnn。
假设想对非首次遇到的元素进行进一步的内层循环,假设找到的方案假设为n′n^{'}n′,此时是不可以的,会导致最终重复的解决方案。

因为S′⊂SS^{'}\subset SS′⊂S,而两者的目标都是一致:寻找到和为7的元素。必然会导致n′⊂nn^{'} \subset nn′⊂n。也即方案的重复,因此对于外层循环,我们仅对首次遇到的元素进行进一步的内层循环。
对于内层循环,与之类似,也是通过跳过重复的元素来,防止方案重复。
3. 解题
class Solution {
public:vector<vector<int>> threeSum(vector<int>& nums) {sort(nums.begin(), nums.end());vector<vector<int>> res;for(int i = 0; i < nums.size(); ++i){if(0 == i || nums[i - 1] != nums[i]){twoSum(nums, i, res);}}return res;}
private:void twoSum(vector<int>& nums, int i, vector<vector<int>> &res){int left = i + 1, right = nums.size() - 1;while(left < right){int sum = nums[i] + nums[left] + nums[right];if(sum < 0){++left;}else if (sum > 0){--right;}else{res.push_back({nums[i], nums[left++], nums[right--]});while(left < right && nums[left - 1] == nums[left])++left;}} }
};
其中,保证了,若以nums[i]为开始(3元素方案),则后续的方案不会重复。
if(0 == i || nums[i - 1] != nums[i]){twoSum(nums, i, res);
该段代码,保证了若以nums[left]为开始(2元素方案),则后续的方案不会重复。
while(left < right && nums[left - 1] == nums[left])++left;
3. 总结
该题相对较难,尤其是消除重复方案这部分,最好以类似于动态规划的思想(假设子问题已解决)来理解。在一定理解的基础上进行记忆。
相关文章:
leetcode: 3Sum
leetcode: 3Sum1. 题目描述2. 思考3. 解题3. 总结1. 题目描述 Given an integer array nums, return all the triplets [nums[i], nums[j], nums[k]] such that i ! j, i ! k, and j ! k, and nums[i] nums[j] nums[k] 0. Notice that the solution set must not contain …...
【Python学习笔记】26.Python3 输入和输出(2)
前言 本章节继续介绍Python的输入输出。 文件对象的方法 本节中剩下的例子假设已经创建了一个称为 f 的文件对象。 f.read() 为了读取一个文件的内容,调用 f.read(size), 这将读取一定数目的数据, 然后作为字符串或字节对象返回。 size 是一个可选的数字类型的…...
vue项目第二天
项目中使用element-ui库中文网https://element.eleme.cn/#/zh-CN安装命令npm install element-ui安装按需加载babel插件npm install babel-plugin-component -Dnpm i //可以通过npm i 的指令让配置刷新重新配置一下项目中使用element-ui组件抽离文件中按需使用element ui &…...
Python爬虫零基础到进阶(课程说明)
Python爬虫零基础到进阶 课程介绍总结 学—练—问 跟着学、多做多练、不懂就问、坚持就是胜利! 作业 飞书布置,作业提交放到群里,老师批改。 代码量 python基础: 十一次课,学会python。环境安装(了…...
《C++ Primer Plus》第16章:string类和标准模板库(13)
复习题 考虑下面的声明: class RQ1{ private:char *st; // pointer to C-style string public:RQ1() { st new char [1];strcpy(st, "");}RQ1(const char * s) {st new char [strlen(s)1];strcpy(st, s);}RQ1(const RQ1 & rq) {st new char[strlen…...
材质笔记 - Simluate Solid Surface
光的行为 当光和物体相遇时,光会有三种行为:被物体反射、穿过物体(物体是透明或半透明的)或者被吸收。 高光反射和漫反射 高光反射(Specular Reflection)会在表面光滑且反光的物体上看到,比如镜…...
设计模式-值类型与引用类型、深拷贝与浅拷贝、原型模式详解
一. 值类型和引用类型 1. 前言 (1). 分类 值类型包括:布尔类型、浮点类型(float、double、decimal、byte)、字符类型(char)、整型(int、long、short等)、枚举(entum)、结构体(struct)。 引用类型:数组、字符串(string)、类、接口…...
ssm高校功能教室预约系统java idea maven
本网站所实现的是一个高校功能教室预约系统,该系统严格按照需求分析制作相关模块,并利用所学知识尽力完成,但是本人由于学识浅薄,无法真正做到让该程序可以投入市场使用,仅仅简单实现部分功能,希望日后还能…...
C语言学习笔记-强制类型转换
强制类型转换是通过类型转换运算来实现的。其一般形式为:(类型说明符)(表达式)其功能是把表达式的运算结果强制转换成类型说明符所表示的类型。自动转换是在源类型和目标类型兼容以及目标类型广于源类型时发生一个类型…...
docker数据卷插件
在docker中,对接外部存储我们通常需要docker的数据卷插件。docker中简要可分为两类 docker卷插件和CSI插件,其中docker卷插件分为两个版本,旧版的传统插件(legacy plugin/non-managed plugin)和新版的托管插件(managed plugin)。下面分章节讨…...
第二章-线程(3)
线程一、线程的定义二、线程的实现一、线程的定义 线程: 线程是进程中的一个实体,是系统独立调度和分派的基本单位。 进程是资源的拥有者,线程是系统独立调度和分配的基本单位。 进程与线程的比较: 调度:线程调度快…...
C++学习记录——칠 类和对象(4)
文章目录1、const成员2、取地址及const取地址操作符重载3、构造函数续集1、初始化列表2、explicit关键字4、static成员5、匿名对象6、友元1.友元函数2、友元类7、内部类1、const成员 看一段代码 class A { public:void Print(){cout << _a << endl;} private:int…...
Python-项目实战--飞机大战-碰撞检测(8)
目标了解碰撞检测方法碰撞实现1.了解碰撞检测方法pygame提供了两个非常方便的方法可以实现碰撞检测:pygame.sprite.groupcollide()两个精灵组中所有的精灵的碰撞检测groupcollide(group1, group2, dokill1, dokill2, collided None) -> Sprite_dict如果将dokill…...
T06 成绩排序
查找和排序 题目:输入任意(用户,成绩)序列,可以获得成绩从高到低或从低到高的排列,相同成绩 都按先录入排列在前的规则处理。 示例: jack 70 peter 96 Tom 70 smith 67 从高到低 成…...
【机器学习】Linear and Nonlinear Regression 线性/非线性回归讲解
文章目录一、回归问题概述二、误差项定义三、独立同分布的假设四、似然函数的作用五、参数求解六、梯度下降算法七、参数更新方法八、优化参数设置一、回归问题概述 回归:根据工资和年龄,预测额度为多少 其中,工资和年龄被称为特征࿰…...
PyQt5数据库开发1 4.1 SQL Server 2008 R2如何开启数据库的远程连接
文章目录 前言 步骤/方法 1 使用windows身份登录 2 启用混合登录模式 3 允许远程连接服务器 4 设置sa用户属性 5 配置服务器 6 重新登录 7 配置SSCM 8 确认防火墙设置 注意事项 前言 SQL Server 2008 R2如何开启数据库的远程连接 SQL Server 2008默认是不允许远程连…...
javassm高校学生评教系统的设计与实现idea msyql
伴随着社会以及科学技术的发展,互联网已经渗透在人们的身边,网络慢慢的变成了人们的生活必不可少的一部分,紧接着网络飞速的发展,管理系统这一名词已不陌生,越来越多的学校、公司等机构都会定制一款属于自己个性化的管…...
为什么神经网络做不了2次函数拟合,网上的都是骗人的吗?
环境:tensorflow2 kaggle 这几天突发奇想,用深度学习训练2次函数。先在网上找找相同的资料这方面资料太少了。大多数如下: 。 给我的感觉就是,用深度学习来做,真的很容易。 网上写出代码分析的比较少。但是也找到了…...
【Java】Help notes about JAVA
JAVA语言帮助笔记Java的安装与JDKJava命名规范JAVA的数据类型自动类型转换强制类型转换JAVA的运算符取余运算结果的符号逻辑运算的短路运算三元运算符运算符优先级JAVA的流程控制分支结构JAVA类Scanner类Java的安装与JDK JDK安装网站:https://www.oracle.com/java/…...
2023北京老博会,北京养老展,第十届中国国际老年产业博览会
2023第十届(北京)国际老年产业博览会,将于08月28-30日盛大举办; 2023北京老博会:2023第十届中国(北京)国际老年产业博览会The 2023 tenth China (Beijing) International Aged industry Expo&a…...
vscode里如何用git
打开vs终端执行如下: 1 初始化 Git 仓库(如果尚未初始化) git init 2 添加文件到 Git 仓库 git add . 3 使用 git commit 命令来提交你的更改。确保在提交时加上一个有用的消息。 git commit -m "备注信息" 4 …...
Vue记事本应用实现教程
文章目录 1. 项目介绍2. 开发环境准备3. 设计应用界面4. 创建Vue实例和数据模型5. 实现记事本功能5.1 添加新记事项5.2 删除记事项5.3 清空所有记事 6. 添加样式7. 功能扩展:显示创建时间8. 功能扩展:记事项搜索9. 完整代码10. Vue知识点解析10.1 数据绑…...
Appium+python自动化(十六)- ADB命令
简介 Android 调试桥(adb)是多种用途的工具,该工具可以帮助你你管理设备或模拟器 的状态。 adb ( Android Debug Bridge)是一个通用命令行工具,其允许您与模拟器实例或连接的 Android 设备进行通信。它可为各种设备操作提供便利,如安装和调试…...
练习(含atoi的模拟实现,自定义类型等练习)
一、结构体大小的计算及位段 (结构体大小计算及位段 详解请看:自定义类型:结构体进阶-CSDN博客) 1.在32位系统环境,编译选项为4字节对齐,那么sizeof(A)和sizeof(B)是多少? #pragma pack(4)st…...
376. Wiggle Subsequence
376. Wiggle Subsequence 代码 class Solution { public:int wiggleMaxLength(vector<int>& nums) {int n nums.size();int res 1;int prediff 0;int curdiff 0;for(int i 0;i < n-1;i){curdiff nums[i1] - nums[i];if( (prediff > 0 && curdif…...
ffmpeg(四):滤镜命令
FFmpeg 的滤镜命令是用于音视频处理中的强大工具,可以完成剪裁、缩放、加水印、调色、合成、旋转、模糊、叠加字幕等复杂的操作。其核心语法格式一般如下: ffmpeg -i input.mp4 -vf "滤镜参数" output.mp4或者带音频滤镜: ffmpeg…...
微信小程序云开发平台MySQL的连接方式
注:微信小程序云开发平台指的是腾讯云开发 先给结论:微信小程序云开发平台的MySQL,无法通过获取数据库连接信息的方式进行连接,连接只能通过云开发的SDK连接,具体要参考官方文档: 为什么? 因为…...
Android Bitmap治理全解析:从加载优化到泄漏防控的全生命周期管理
引言 Bitmap(位图)是Android应用内存占用的“头号杀手”。一张1080P(1920x1080)的图片以ARGB_8888格式加载时,内存占用高达8MB(192010804字节)。据统计,超过60%的应用OOM崩溃与Bitm…...
AI,如何重构理解、匹配与决策?
AI 时代,我们如何理解消费? 作者|王彬 封面|Unplash 人们通过信息理解世界。 曾几何时,PC 与移动互联网重塑了人们的购物路径:信息变得唾手可得,商品决策变得高度依赖内容。 但 AI 时代的来…...
安宝特案例丨Vuzix AR智能眼镜集成专业软件,助力卢森堡医院药房转型,赢得辉瑞创新奖
在Vuzix M400 AR智能眼镜的助力下,卢森堡罗伯特舒曼医院(the Robert Schuman Hospitals, HRS)凭借在无菌制剂生产流程中引入增强现实技术(AR)创新项目,荣获了2024年6月7日由卢森堡医院药剂师协会࿰…...
