当前位置:网站首页>[Leetcode15]三数之和
[Leetcode15]三数之和
2022-07-06 09:17:00 【劲腰傩舞】
个人向,仅作记录回顾
双指针
问题
给你一个包含 n 个整数的数组 nums,判断 nums 中是否存在三个元素 a,b,c ,使得 a + b + c = 0 ?请你找出所有和为 0 且不重复的三元组。
注意:答案中不可以包含重复的三元组。
示例 1:
输入:nums = [-1,0,1,2,-1,-4]
输出:[[-1,-1,2],[-1,0,1]]
示例 2:
输入:nums = []
输出:[]
示例 3:
输入:nums = [0]
输出:[]
提示:
0 <= nums.length <= 3000
-105 <= nums[i] <= 105
来源:力扣(LeetCode)
链接:https://leetcode.cn/problems/3sum
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
vector<vector<int>> threeSum(vector<int>& nums) {
/* * 题目给了一个数组。要求枚举出所有三个数字相加等于零的组合。且组合不能重复。 * 直接用三重循环枚举的话。需要额外判断组合之间是否重复。 * 如果先对nums进行排序。要求枚举出来的三个数字有a<=b<=c。那么就可以避免重复。 */
sort(nums.begin(), nums.end());
/*获取nums大小。即将开始枚举。*/
int size = nums.size();
//存放结果
vector<vector<int>> ans;
for (int first = 0; first < size; first++) {
//在first=n-1的时候。开不出第二个for循环。
/*为了避免枚举出的组合的重复*/
if (first > 0 && nums[first] == nums[first - 1])
continue;
/*目标是三个数字的和等于零。那么随着second这个下标越来越大。third越来越小。 * 开始双指针。先初始化third */
int third = size - 1;
for (int second = first + 1; second < size; second++) {
/*还是为了避免枚举出的组合的重复*/
if (second > first + 1 && nums[second] == nums[second - 1])
continue;
/*还是先避免组合的重复*/
while (third > second && third < size - 1 && nums[third] == nums[third + 1])
third--;
/*不满足条件的话,继续左移third*/
while (third > second && nums[third] + nums[second] > -nums[first])
third--;
/*双指针重叠的时候。second指针继续右移的话。也不会再满足题意了 * 但是first还可以继续右移。 */
if (third == second)
break;
if (nums[third] + nums[second] == -nums[first])
/*初始化vector<int>的一种好用的方法{1,2,3}*/
ans.push_back({
nums[first],nums[second],nums[third] });
/*小于的情况不用考虑了。继续右移second就能解决*/
}
}
return ans;
}
边栏推荐
- arduino UNO R3的寄存器写法(1)-----引脚电平状态变化
- Who says that PT online schema change does not lock the table, or deadlock
- ESP8266通过Arduino IDE连接Onenet云平台(MQTT)
- js题目:输入数组,最大的与第一个元素交换,最小的与最后一个元素交换,输出数组。
- .elf .map .list .hex文件
- ES6语法总结--下篇(进阶篇 ES6~ES11)
- Mysql database interview questions
- Redis 缓存更新策略,缓存穿透、雪崩、击穿问题
- Mp3mini playback module Arduino < dfrobotdfplayermini H> function explanation
- Variable parameter principle of C language function: VA_ start、va_ Arg and VA_ end
猜你喜欢
Redis 缓存更新策略,缓存穿透、雪崩、击穿问题
JS数组常用方法的分类、理解和运用
MySQL时间、时区、自动填充0的问题
数据库课程设计:高校教务管理系统(含代码)
Redis cache update strategy, cache penetration, avalanche, breakdown problems
Arduino JSON data information parsing
Basic operations of databases and tables ----- classification of data
Types de variables JS et transformations de type communes
高通&MTK&麒麟 手機平臺USB3.0方案對比
Fashion-Gen: The Generative Fashion Dataset and Challenge 论文解读&数据集介绍
随机推荐
MySQL takes up too much memory solution
Arm pc=pc+8 is the most understandable explanation
Arduino gets the length of the array
Working principle of genius telephone watch Z3
Oppo vooc fast charging circuit and protocol
imgcat使用心得
Embedded startup process
PT OSC deadlock analysis
單片機藍牙無線燒錄
Basic operations of databases and tables ----- classification of data
Page performance optimization of video scene
Stm32f1+bc20+mqtt+freertos system is connected to Alibaba cloud to transmit temperature and humidity and control LED lights
(一)R语言入门指南——数据分析的第一步
Esp8266 connects to bafayun (TCP maker cloud) through Arduino IED
Classification, understanding and application of common methods of JS array
ESP学习问题记录
Gravure sans fil Bluetooth sur micro - ordinateur à puce unique
[esp32 learning-2] esp32 address mapping
Symbolic representation of functions in deep learning papers
Walk into WPF's drawing Bing Dwen Dwen