Question:
Given an arraySofnintegers, are there elementsa,b,cinSsuch thata+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)
Anwser 1:
class Solution {
public:
vector<vector<int> > threeSum(vector<int> &num) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
vector< vector<int> > ret;
int len = num.size();
if(len < 3) return ret;
vector<int> num2;
num2.assign(num.begin(), num.end());
sort( num2.begin(), num2.end() ); // sort O(n*log(n))
vector<int> tmpRet(3);
tmpRet[0] = num2[0] - 1;
for(int i = 0; i < len - 2; i++){ // O(n*m)
int l = i + 1;
int r = len - 1;
if(num2[i] == tmpRet[0]) continue;
tmpRet[0] = num2[i];
while(l < r) {
int sum2 = num2[l] + num2[r];
if(num2[i] + sum2 == 0){
tmpRet[1] = num2[l];
tmpRet[2] = num2[r];
ret.push_back(tmpRet);
while(num2[++l] == num2[l-1] && l < r); // remove same number
while(num2[--r] == num2[r+1] && l < r);
} else if(num2[i] + sum2 < 0){
l++;
} else {
r--;
}
}
}
return ret;
}
};
分享到:
相关推荐
双指针算法,python数组双指针算法求和问题LeetCode2sum3sum4sum含代码
文档python数组双指针算法求和问题LeetCode2sum3sum4sum含代码提取方式是百度网盘分享地址
3sum 力码 力扣算法 (注:“ :locked: " 表示你需要来自 Leetcode) # 标题 解决方案 困难 001 简单的 002 中等的 003 中等的 004 难的 005 中等的 006 简单的 007 简单的 008 简单的 009 简单的 010 难的 011 中等...
3sum leetcode-curation-topical 精选 Leetcode 问题,按主题/概念分类。 我的策展标准是问题必须是有价值的,而不仅仅是为了难而难。 有价值的问题通常可以以不同的时间/空间效率(通过使用各种数据结构)以多种...
Leetcode two sum java 解法
3sum nlogn 让我们研究算法 微电脑网 : 2018.09.06。 用 BFS 搜索,用 DP 解决。 我过去没能做到,但感觉很好。 : 2018.09.06。 起初,它以这样的方式重复,如果有什么变化,它会再次旋转。 -> 超时 接下来,只将...
oj.leetcode题解, 2sum, 运用hashtable解决这到问题,时间复杂度O(N)
leetcode 2sum leetCode解决方案 我对 leetCode 问题的解决方案 已解决的练习列表: 简单的: ...3Sum - 效果不错,但仍需调整; O(n2) 复杂度; 花了~51ms 盛水最多的容器; O(n) 复杂度 难的: ?
3sum nlogn LeetCode 刷LeetCode题目思路 1.经典题目2SUM,利用hash_map完成 已知俩数之和,求能组成这个和的数字在数组中的下标 以数组中的值为key value,下标为value,即能实现常数级的复杂度 2.3Sum 题目同上,三...
3sum nlogn 编码问题 审查旧代码与早晨咖啡/茶搭配得很好;) Leetcode - DS & Alg : 链表,最小堆 : 二分查找 : 数组,动态规划 : 数组,Kadane 算法 : 树遍历 : 二叉树 : 二叉树 : 二叉树、队列、bfs : 字符串操作 ...
leetcode 2SUM 使用以前的地图最快的 2Sum O(N) 使用 unordered_map 比 map 快 以前的地图 là gì ? 上一张地图 đơn giản là 地图 nhưng thay vì ta cần một vòng for để khởi tạo 地图 thì ta khởi...
LC3: Longest Substring Without Repeating Characters [Medium] LC4: Longest Palindromic Substring [Medium] LC5: Median Of Two Sorted Arrays [Hard] LC6: Zigzag Conversion [Medium] LC7: Reverse Integer ...
leetcode 2sum 2总和 力码研究1
3sum nlogn leetcode ny leetcode notebook time space c/c++ Time limite 1s - 2s data scale (n=* ) time complesity( O(*) ) example <=30 2^n expensial,dfs+cut 10^2 n^3 floyed 10^3 n^2, n^2*logn ...
3sum nlogn 面试准备 我在 LeetCode、AlgoExpert、Codewars、EPI book、Pramp、Codility 和其他面试准备资源上的编码面试问题的解决方案。 从 2020 年 10 月 20 日开始,我将每天将我的解决方案添加到此存储库中。 ...
3sum nlogn 力码 LeetCode 问题的解决方案。 尝试用所有语言解决它们。 地位 语言 构建状态 解决的问题 C C++ C# Java JavaScript Python Ruby 问题 # 标题 解决方案 时间 空间 注释 1 (4ms) (16ms) (496ms) (324ms...
3sum nlogn 标签: to-do list 书目评论 利特码攻占清朝 标题 我的时间复杂度 最佳时间复杂度 编程语言 日期 上) 上) Python 2020/02/29 上) 上) Python 2020/02/21 O(N^2) O(N^2) Python 2020/02/19 上) 上) ...
3sum nlogn 力码 LeetCode 问题的 JavaScript 解决方案。 问题 目录 问题 001-050 # 标题 解决方案 时间 空间 注释 1 二和 (72 毫秒) 上) 上) 2 两个数字相加 (260 毫秒) O(Max(N, M)) O(1) 3 无重复字符的最长...
3sum nlogn 话题 比赛 否 网站 问题 解决方案(Java) 解决方案(Python) 日期 1 力码 16-11-19 2 力码 —— 17-11-19 3 力码 —— 17-11-19 4 力码 —— 24-11-19 5 力码 —— 24-11-19 6 力码 —— 30-11-19 7 力码 ...
3sum nlogn class Solution { public: int threeSumClosest(vector &num, int target) { /* O(nlogn) + O(n^2) = O(n^2) */ int result = 0, diff = INT_MAX; sort(num.begin(), num.end()); const int n = num.size...