当前位置:网站首页>[leetcode15] sum of three numbers
[leetcode15] sum of three numbers
2022-07-06 12:24:00 【Vigorous waist Nuo dance】
Personally to , For record review only
Double pointer
problem
Give you one containing n Array of integers nums, Judge nums Are there three elements in a,b,c , bring a + b + c = 0 ? Please find out all and for 0 Triple without repetition .
Be careful : Answer cannot contain duplicate triples .
Example 1:
Input :nums = [-1,0,1,2,-1,-4]
Output :[[-1,-1,2],[-1,0,1]]
Example 2:
Input :nums = []
Output :[]
Example 3:
Input :nums = [0]
Output :[]
Tips :
0 <= nums.length <= 3000
-105 <= nums[i] <= 105
source : Power button (LeetCode)
link :https://leetcode.cn/problems/3sum
Copyright belongs to the network . For commercial reprint, please contact the official authority , Non-commercial reprint please indicate the source .
vector<vector<int>> threeSum(vector<int>& nums) {
/* * The title gives an array . Ask Mei to cite the combination of all three numbers that add up to zero . And the combination cannot be repeated . * If you use triple loop enumeration directly . Additional judgment is needed to determine whether the combinations are repeated . * If you're right first nums Sort . The three numbers required to be enumerated are a<=b<=c. Then you can avoid repetition . */
sort(nums.begin(), nums.end());
/* obtain nums size . About to start enumerating .*/
int size = nums.size();
// Store results
vector<vector<int>> ans;
for (int first = 0; first < size; first++) {
// stay first=n-1 When . Can't open the second one for loop .
/* In order to avoid the repetition of the combination of Meiju */
if (first > 0 && nums[first] == nums[first - 1])
continue;
/* The goal is that the sum of three numbers equals zero . Then, along with second This subscript is getting bigger .third It's getting smaller . * Start with two pointers . Initialize first third */
int third = size - 1;
for (int second = first + 1; second < size; second++) {
/* Or to avoid the repetition of the combination of Meiju */
if (second > first + 1 && nums[second] == nums[second - 1])
continue;
/* Or first avoid the repetition of the combination */
while (third > second && third < size - 1 && nums[third] == nums[third + 1])
third--;
/* If the conditions are not met , Continue to move left third*/
while (third > second && nums[third] + nums[second] > -nums[first])
third--;
/* When double pointers overlap .second If the pointer continues to move to the right . It won't satisfy the meaning of the topic anymore * however first You can also continue to move right . */
if (third == second)
break;
if (nums[third] + nums[second] == -nums[first])
/* initialization vector<int> An easy way to use {1,2,3}*/
ans.push_back({
nums[first],nums[second],nums[third] });
/* The case of less than does not need to be considered . Keep moving right second It can be solved */
}
}
return ans;
}
边栏推荐
- How to add music playback function to Arduino project
- (1) Introduction Guide to R language - the first step of data analysis
- Redis based distributed ID generator
- Minio file download problem - inputstream:closed
- [Red Treasure Book Notes simplified version] Chapter 12 BOM
- [Leetcode15]三数之和
- Imgcat usage experience
- Basic operations of databases and tables ----- view data tables
- GCC compilation options
- Redis based distributed locks and ultra detailed improvement ideas
猜你喜欢
ES6语法总结--下篇(进阶篇 ES6~ES11)
Remember an experience of ECS being blown up by passwords - closing a small black house, changing passwords, and changing ports
Fashion Gen: the general fashion dataset and challenge paper interpretation & dataset introduction
[esp32 learning-1] construction of Arduino esp32 development environment
Understanding of AMBA, AHB, APB and Axi
(三)R语言的生物信息学入门——Function, data.frame, 简单DNA读取与分析
(四)R语言的数据可视化——矩阵图、柱状图、饼图、散点图与线性回归、带状图
Kaggle competition two Sigma connect: rental listing inquiries (xgboost)
Symbolic representation of functions in deep learning papers
Whistle+switchyomega configure web proxy
随机推荐
如何给Arduino项目添加音乐播放功能
MySQL占用内存过大解决方案
JS Title: input array, exchange the largest with the first element, exchange the smallest with the last element, and output array.
Problèmes avec MySQL time, fuseau horaire, remplissage automatique 0
Mysqldump error1066 error solution
Talking about the startup of Oracle Database
Types de variables JS et transformations de type communes
Symbolic representation of functions in deep learning papers
AMBA、AHB、APB、AXI的理解
Learning notes of JS variable scope and function
JS变量类型以及常用类型转换
[Nodejs] 20. Koa2 onion ring model ----- code demonstration
单片机蓝牙无线烧录
Minio file download problem - inputstream:closed
Navigator object (determine browser type)
Pytorch: tensor operation (I) contiguous
[Offer29] 排序的循环链表
[golang] leetcode intermediate - fill in the next right node pointer of each node & the k-smallest element in the binary search tree
open-mmlab labelImg mmdetection
ES6 grammar summary -- Part I (basic)