leetcode 15. 3Sum
解释：
在一个数组中，找出三个数，这三个数的和为0。
思路：
可以看成这样的问题：a+b = - c
这样就是从数组中找出两个数之和为-c的两个数了。
首先对数组进行排序。
之后一个for遍历数组，得到不同的c值。
在数组头与尾插入两个指示index_i，index_j。
当这两个指示所指示的数的和小于-c，那么增大index_i，使数字和变大。
当这两个指示所指示的数的和大于-c，那么减小index_j，使数字和变小。
注意这个数组不能有重复，因此用先用set进行插入（set无重复元素），最后再复制到vector当中。
而且set中的每个元素需要按升序排列，在插入前判断一下大小顺序后，再插入。
class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums) {
set<vector<int>> result;
sort(nums.begin(),nums.end());
for(int i = 0; i < nums.size(); i++){
if(nums.size()<3)
break;
if(i > 0 && nums.at(i) == nums.at(i-1) && i < nums.size()-1)
continue;
int c = nums.at(i);
int index_i = 0;
int index_j = nums.size()-1;
while(index_i < index_j){
if(index_i == i)
{
index_i++;
continue;
}
if(index_j == i)
{
index_j--;
continue;
}
if(nums.at(index_i) + nums.at(index_j) < -1*c)
index_i++;
else if(nums.at(index_i) + nums.at(index_j) > -1*c)
index_j--;
else
{
if(index_i < i&& i < index_j)
{
vector<int> temp;
temp.push_back(nums.at(index_i));
temp.push_back(nums.at(i));
temp.push_back(nums.at(index_j));
result.insert(temp);
}else if(index_j < i){
vector<int> temp;
temp.push_back(nums.at(index_i));
temp.push_back(nums.at(index_j));
temp.push_back(nums.at(i));
result.insert(temp);
}else if(i < index_i){
vector<int> temp;
temp.push_back(nums.at(i));
temp.push_back(nums.at(index_i));
temp.push_back(nums.at(index_j));
result.insert(temp);
}
index_i++;
index_j--;
}
}
}
vector<vector<int>> s;
insert_iterator<vector<vector<int>>> in_it(s, s.begin());
copy(result.begin(), result.end(), in_it);
return s;
}
};
相关知识
Python Leetcode(905.按奇偶排序数组)
leetcode
15.犯罪形态（二）2020年法考刑法精讲班柏浪涛（系统强化班）
二、或运算的最小翻转次数（Weekly Contest 171）
初学C语言【14】寻找单身狗
【题目】15.(★★★2014,大兴模拟)如图,要
23届非科班选手秋招转码指南
论宠物的正确用法 15.怪物……？走你！ 最新更新
动物病理
15．人们受小鸟在空中飞翔的启发而发明了飞机.小鸟扇动翅膀.获得向上的举力可表示为F＝.式中S为翅膀的面积.V为小鸟的飞行速度.K为比例系数.一个质量为100克.翅膀长为a.宽为b的燕子.其最小的飞翔——青夏教育精英家教网——
网址: leetcode 15. 3Sum https://m.mcbbbk.com/newsview411742.html
| 上一篇: 步步为营 |
下一篇: Petcube：通过手机远程和宠 |
