当前位置:网站首页>[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;
}
边栏推荐
- Kconfig Kbuild
- PT OSC deadlock analysis
- VIM command line notes
- Important methods of array and string
- History object
- Programmers can make mistakes. Basic pointers and arrays of C language
- (1) Introduction Guide to R language - the first step of data analysis
- Classification, understanding and application of common methods of JS array
- Symbolic representation of functions in deep learning papers
- (三)R语言的生物信息学入门——Function, data.frame, 简单DNA读取与分析
猜你喜欢
Single chip Bluetooth wireless burning
Whistle+switchyomega configure web proxy
Several declarations about pointers [C language]
[golang] leetcode intermediate - fill in the next right node pointer of each node & the k-smallest element in the binary search tree
Remember an experience of ECS being blown up by passwords - closing a small black house, changing passwords, and changing ports
js 变量作用域和函数的学习笔记
dosbox第一次使用
Kconfig Kbuild
Postman 中级使用教程【环境变量、测试脚本、断言、接口文档等】
Redis based distributed ID generator
随机推荐
如何给Arduino项目添加音乐播放功能
Remember an experience of ECS being blown up by passwords - closing a small black house, changing passwords, and changing ports
Common DOS commands
Kaggle competition two Sigma connect: rental listing inquiries
Arduino get random number
(一)R语言入门指南——数据分析的第一步
2021.11.10汇编考试
JS variable types and common type conversions
(三)R语言的生物信息学入门——Function, data.frame, 简单DNA读取与分析
[golang] leetcode intermediate - fill in the next right node pointer of each node & the k-smallest element in the binary search tree
[Nodejs] 20. Koa2 onion ring model ----- code demonstration
列表的使用
Feature of sklearn_ extraction. text. CountVectorizer / TfidVectorizer
(五)R语言入门生物信息学——ORF和序列分析
JS Title: input array, exchange the largest with the first element, exchange the smallest with the last element, and output array.
Walk into WPF's drawing Bing Dwen Dwen
MySQL時間、時區、自動填充0的問題
ORA-02030: can only select from fixed tables/views
Keyword inline (inline function) usage analysis [C language]
ESP8266连接onenet(旧版MQTT方式)