一天一道LeetCode系列
(一)题目
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.
For example, given array S = {-1 0 1 2 -1 -4}, A solution set is: (-1, 0, 1) (-1, -1, 2)
(二)解题
这道题的关键在于:结果集合中不允许有重复。
想到的方法有两个:1、在查找过程中去重 2、在结果中去重
经过试验,结果中去重会直接超时。
1、过程中去重版本
class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums) {
vector<vector<int>> vecresult;
std::sort(nums.begin(),nums.end());
int len = nums.size();
if(len <3) return vecresult;
for(int i = 0 ; i < nums.size() ;)
{
if(nums[i]>0) return vecresult;
for(int j = i+1;j<nums.size()-1;)
{
int temp = 0-nums[i]-nums[j];
vector<int>::iterator iter = find(nums.begin()+j+1,nums.end(),temp);
if(iter != nums.end())
{
vector<int> tempres;
tempres.push_back(nums[i]);
tempres.push_back(nums[j]);
tempres.push_back(*iter);
vecresult.push_back(tempres);
}
j++;
while(j<nums.size()&&nums[j]==nums[j-1]) ++j;//去重
}
i++;
while(i<nums.size()&&nums[i]==nums[i-1]) ++i;//去重
}
return vecresult;
}
};
2、结果中去重版本(超时)
class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums) {
vector<vector<int>> vecresult;
std::sort(nums.begin(),nums.end());
int len = nums.size();
if(len <3) return vecresult;
for(int i = 0 ; i < nums.size() ; i++)
{
if(nums[i]>0) return vecresult;
for(int j = i+1;j<nums.size()-1;j++)
{
int temp = 0-nums[i]-nums[j];
vector<int>::iterator iter = find(nums.begin()+j+1,nums.end(),temp);
if(iter != nums.end())
{
vector<int> tempres;
tempres.push_back(nums[i]);
tempres.push_back(nums[j]);
tempres.push_back(*iter);
if(vecresult.size()==0)
{
vecresult.push_back(tempres);
}
else{
vector<vector<int>>::iterator it1 = find(vecresult.begin(),vecresult.end(),tempres);
if(it1 == vecresult.end())//结果中去重
{
vecresult.push_back(tempres);
}
}
}
}
}
return vecresult;
}
};
【一天一道LeetCode】#15 3Sum的更多相关文章
-
LeetCode 15 3Sum [sort] <;c++>;
LeetCode 15 3Sum [sort] <c++> 给出一个一维数组,找出其中所有和为零的三元组(元素集相同的视作同一个三元组)的集合. C++ 先自己写了一发,虽然过了,但跑了3 ...
-
leetcode 15. 3Sum 二维vector
传送门 15. 3Sum My Submissions Question Total Accepted: 108534 Total Submissions: 584814 Difficulty: Me ...
-
每日一道 LeetCode (15):二进制求和
每天 3 分钟,走上算法的逆袭之路. 前文合集 每日一道 LeetCode 前文合集 代码仓库 GitHub: https://github.com/meteor1993/LeetCode Gitee ...
-
[LeetCode] 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 un ...
-
LeetCode——15. 3Sum
一.题目链接:https://leetcode.com/problems/3sum/ 二.题目大意: 3和问题是一个比较经典的问题,它可以看做是由2和问题(见http://www.cnblogs.co ...
-
LeetCode 15 3Sum(3个数求和为0的组合)
题目链接 https://leetcode.com/problems/3sum/?tab=Description Problem: 给定整数集合,找到所有满足a+b+c=0的元素组合,要求该组合不 ...
-
LeetCode 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 un ...
-
LeetCode 15. 3Sum 16. 3Sum Closest 18. 4Sum
n数求和,固定n-2个数,最后两个数在连续区间内一左一右根据当前求和与目标值比较移动,如果sum<target,移动较小数,否则,移动较大数 重复数处理: 使i为左至右第一个不重复数:while ...
-
leetCode 15. 3Sum (3数之和) 解题思路和方法
3Sum Given an array S of n integers, are there elements a, b, c in S such that a + b + c = 0? Find ...
-
leetcode 15 3sum &; leetcode 18 4sum
3sum: 1 class Solution { public: vector<vector<int>> threeSum(vector<int>& num ...
随机推荐
-
VB.NET设置控件和窗体的显示级别
前言:在用VB.NET开发射频检测系统ADS时,当激活已存在的目标MDI子窗体时,被其他子窗体遮住了,导致目标MDI子窗体不能显示. 这个问题怎么解决呢?网上看到一篇帖子VB.NET设置控件和窗体的显 ...
-
c# 三种常见的委托
参考 <编写高质量代码:改善C#程序的157个建议> , 尽量使用FCL中的委托声明. FCL: FrameWork Class Library 三种常用:Action.Func.Pre ...
-
vs出现“已经在解决方案中打开了具有该名称的项目”问题的解决方案
经过本人测试,这种问题一般出现在装了svn的项目. 其实删除了删除sln和csproj文件中的SVN配置信息就行了 需要删除的信息 sln文件中: GlobalSection(SubversionSc ...
-
Combination Sum II [LeetCode]
Problem description: http://oj.leetcode.com/problems/combination-sum-ii/ Basic idea: use recursive a ...
-
Log Explorer使用说明
一.介绍 Log Explorer主要用于对MSSQLServer的事物分析和数据恢复.你可以浏览日志.导出数据.恢复被修改或者删除的数据(包括执行过update,delete,drop和trunca ...
-
Linq/EF/lambda Group by/Order by 多个字段详细用法
1)单个字段Group by: //a.Key类型与a.Province字段类型一样 .GroupBy(a => a.Province).Select(a => a.Key).ToLis ...
-
openfire学习4------->;android客户端聊天开发之聊天功能开发
前面我们已经把服务器搭建完成,并且在客户端实现了登录了. 和我们使用的QQ一样,想一想,登录成功之后呢?肯定是要有一个好友列表,通过这个列表,我们可以选择我们需要聊天的好友. 这里我们先研究下 xmp ...
-
pycharm clion phpstorn全家桶激活码(可以用到2019年4月)
SXXI7H41YN-eyJsaWNlbnNlSWQiOiJTWFhJN0g0MVlOIiwibGljZW5zZWVOYW1lIjoicGF5bmUgd2FuZyIsImFzc2lnbmVlTmFtZ ...
-
[C++] 用Xcode来写C++程序[3] Constants
用Xcode来写C++程序[3] Constants 以下是一些基本数据的含义: 75 // int 75u // unsigned int 75l // long 75ul // unsigned ...
-
PyQt 5控件
PyQt 5控件包括:按钮.复选框.滑动条.列表框等 复选框QCheckBox QCheckBox复选框控件,它有两个状态:打开和关闭,他是一个带有文本标签(Label)的控件.复选框常用于表示程序中 ...