# 15.3Sum

Given an array S of n integers, are there elements a, b, c in S such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero.

Note: (Elements in a triplet (a,b,c) must be in non-descending order. (ie, a ≤ b ≤ c))The solution set must not contain duplicate triplets.

For example, given array S = [-1, 0, 1, 2, -1, -4],

A solution set is:
[
[-1, 0, 1],
[-1, -1, 2]
]


1. 以数组形式返回
2. 返回结果不能重复
3. 返回结果以升序排列

for(left=0;left<size&&nums[left]<=0;left++)


while(mid<right){
if(nums[mid]+nums[right]==tmp){
int tmp_left=nums[left],tmp_right=nums[right],tmp_mid=nums[mid];
vector<int>triplet(3,0);
triplet[0]=nums[left];
triplet[1]=nums[mid];
triplet[2]=nums[right];
res.push_back(triplet);
}
else if(nums[mid]+nums[right]<tmp)
mid++;
else
right--;
}


for(left=0;left<size&&nums[left]<=0;left++){
tmp=0-nums[left];
mid=left+1;
right=size-1;
while(mid<right){
if(nums[mid]+nums[right]==tmp){
int tmp_left=nums[left],tmp_right=nums[right],tmp_mid=nums[mid];
vector<int>triplet(3,0);
triplet[0]=nums[left];
triplet[1]=nums[mid];
triplet[2]=nums[right];
res.push_back(triplet);
while(mid<right&&nums[++mid]==tmp_mid);/*防止mid造成重复*/
while(mid<right&&nums[--right]==tmp_right);/*防止right造成重复*/
}
else if(nums[mid]+nums[right]<tmp)
mid++;
else
right--;
}
while(left+1<size&&nums[left]==nums[left+1])/*防止*/
left++;
}


### 学籍管理系统文档

#### 北邮教务系统评教脚本

Published on September 17, 2017

#### 72.Edit distance

Published on September 17, 2017