当前位置:网站首页>[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;
}
边栏推荐
- A possible cause and solution of "stuck" main thread of RT thread
- @The difference between Autowired and @resource
- Mp3mini playback module Arduino < dfrobotdfplayermini H> function explanation
- Kconfig Kbuild
- CUDA C programming authoritative guide Grossman Chapter 4 global memory
- AMBA、AHB、APB、AXI的理解
- [leetcode622]设计循环队列
- Minio file download problem - inputstream:closed
- 2022.2.12 resumption
- ES6 grammar summary -- Part I (basic)
猜你喜欢
I2C bus timing explanation
Types de variables JS et transformations de type communes
Kconfig Kbuild
Cannot change version of project facet Dynamic Web Module to 2.3.
JS變量類型以及常用類型轉換
js 变量作用域和函数的学习笔记
基于Redis的分布式锁 以及 超详细的改进思路
[esp32 learning-2] esp32 address mapping
Programmers can make mistakes. Basic pointers and arrays of C language
Symbolic representation of functions in deep learning papers
随机推荐
JS Title: input array, exchange the largest with the first element, exchange the smallest with the last element, and output array.
记一次云服务器被密码爆破的经历——关小黑屋、改密码、改端口
js题目:输入数组,最大的与第一个元素交换,最小的与最后一个元素交换,输出数组。
MP3mini播放模块arduino<DFRobotDFPlayerMini.h>函数详解
VIM command line notes
level16
STM32 how to locate the code segment that causes hard fault
Esp8266 uses Arduino to connect Alibaba cloud Internet of things
dosbox第一次使用
Feature of sklearn_ extraction. text. CountVectorizer / TfidVectorizer
Kconfig Kbuild
Fashion Gen: the general fashion dataset and challenge paper interpretation & dataset introduction
.elf .map .list .hex文件
ESP learning problem record
Common properties of location
Symbolic representation of functions in deep learning papers
MySQL时间、时区、自动填充0的问题
Classification, understanding and application of common methods of JS array
Arduino get random number
【ESP32学习-2】esp32地址映射