【题目】
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)
Discuss
【题意】
给定n个整数的数组S,是否在 数组S中有元素a,b,C,使得A + B + C =0?在数组中找出独一无二的三元素组,使得他们之和为0。
注意:
在三元素组(A,B,C)中,必须满足非递减排序。 (即A≤B≤C)
该解决方案集中一定不能包含重复的三元素组。
【分析】
先排序,然后二分查找,复杂度 O(n^2*log n)。a + b + c = 0 即 b + c = -a
题目思路与 剑指Offer之和为S的连续正数序列博文思路一致。可以参考一下解题思路。
另有:点击打开链接 详细总结
【代码】
/*********************************
* 日期:2014-01-18
* 作者:SJF0115
* 题号: 3Sum
* 来源:http://oj.leetcode.com/problems/3sum/
* 结果:AC
* 来源:LeetCode
* 总结:
**********************************/
#include <iostream>
#include <stdio.h>
#include <vector>
#include <algorithm>
using namespace std;
class Solution {
public:
vector<vector<int> > threeSum(vector<int> &num) {
int i,j,target,start,end;
int Len = num.size();
vector<int> triplet;
vector<vector<int>> triplets;
//排序
sort(num.begin(),num.end());
for(i = 0;i < Len-2;i++){
//跳过重复元素
if(i != 0 && num[i] == num[i-1]){
continue;
}
//a + b + c = 0
target = -num[i];
//二分查找
start = i + 1;
end = Len - 1;
while(start < end){
int curSum = num[start] + num[end];
//相等 -> 目标
if(target == curSum){
triplet.clear();
triplet.push_back(num[i]);
triplet.push_back(num[start]);
triplet.push_back(num[end]);
triplets.push_back(triplet);
//注意: 跳过重复元素
while(start < end && num[start] == num[start + 1]){
start ++;
}
while(start < end && num[end] == num[end - 1]){
end --;
}
start ++;
end --;
}
//大于 -> 当前值小需要增大
else if(target > curSum){
//注意:跳过重复元素
while(start < end && num[start] == num[start + 1]){
start ++;
}
start ++;
}
//小于 -> 当前值大需要减小
else{
//注意:跳过重复元素
while(start < end && num[end] == num[end - 1]){
end --;
}
end --;
}
}//while
}//for
return triplets;
}
};
int main() {
vector<vector<int>> result;
Solution solution;
vector<int> vec;
vec.push_back(-2);
vec.push_back(0);
vec.push_back(0);
vec.push_back(2);
vec.push_back(2);
result = solution.threeSum(vec);
for(int i = 0;i < result.size();i++){
for(int j = 0;j < result[i].size();j++){
printf("%d ",result[i][j]);
}
printf("\n");
}
return 0;
}
【测试】
Input: |
[-2,0,0,2,2] |
|
|
Expected: |
[[-2,0,2]] |
分享到:
相关推荐
双指针算法,python数组双指针算法求和问题LeetCode2sum3sum4sum含代码
文档python数组双指针算法求和问题LeetCode2sum3sum4sum含代码提取方式是百度网盘分享地址
Leetcode two sum java 解法
3sum leetcode-练习 算法实践 15. 3和 给定一个由 n 个整数组成的数组 nums,nums 中是否有元素 a、b、c 使得 a + b + c = 0? 在数组中找到所有唯一的三元组,其总和为零。 示例输入: [-1, 0, 1, 2, -1, -4] 示例...
3sum # Leetcode 解决方案以下是我在 Leetcode 上解决的一些问题,如果你喜欢/找到任何你的答案,请留下一个星。 如果你想与我联系,我在下面分享了我的 Linkedin URL。 问题 # 标题 # 解决方案 困难 1 二和 简单...
oj.leetcode题解, 2sum, 运用hashtable解决这到问题,时间复杂度O(N)
python python_leetcode面试题解之三数之和_3sum
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...
python python_leetcode面试题解之两数之和TwoSum
LeetCode — Path Sum III分析及实现方法 题目描述: You are given a binary tree in which each node contains an integer value. Find the number of paths that sum to a given value. The path does not need...
3sum2.cpp - 3sum.cpp - BST_from_preorder_traversal.cpp - 2sum.cpp - remove_adjacent_duplicates.cpp - 子集.cpp - 子集_2.cpp - Remove_Nth_Node_From_End_of_List.cpp - invert_Binary_Tree.cpp - 对称树.cpp ...
主要介绍了LeetCode -- Path Sum III分析及实现方法的相关资料,希望通过本文能帮助到大家,需要的朋友可以参考下
16 | [3 Sum Closest](https://leetcode.com/problems/3sum-closest/) | [C++](./C++/3sum-closest.cpp) [Python](./Python/3sum-closest.py) | _O(n^2)_ | _O(1)_ | Medium || Two Pointers 18| [4 Sum]...
答案LeetCode_1_TwoSum LeetCode 问题:给定一个整数数组,找出两个数字,使它们相加为特定的目标数字。 函数 twoSum 应该返回两个数字的索引,使它们相加为目标,其中 index1 必须小于 index2。 请注意,您返回的...
3sum 力码 力扣算法 (注:“ :locked: " 表示你需要来自 Leetcode) # 标题 解决方案 困难 001 简单的 002 中等的 003 中等的 004 难的 005 中等的 006 简单的 007 简单的 008 简单的 009 简单的 010 难的 011 中等...
Sum II - Input array is sorted LeetCode 344 Reverse String LeetCode 345 Reverse Vowels of a String 2 字符串 编号 题目 LeetCode 3 Longest Substring Without Repeating Characters LeetCode 13 Roman to ...
leetcode 2sum leetCode解决方案 我对 leetCode 问题的解决方案 已解决的练习列表: 简单的: ...3Sum - 效果不错,但仍需调整; O(n2) 复杂度; 花了~51ms 盛水最多的容器; O(n) 复杂度 难的: ?
Leetcode 1 two sum C++ code
3sum nlogn 让我们研究算法 微电脑网 : 2018.09.06。 用 BFS 搜索,用 DP 解决。 我过去没能做到,但感觉很好。 : 2018.09.06。 起初,它以这样的方式重复,如果有什么变化,它会再次旋转。 -> 超时 接下来,只将...
The function twoSum should return indices of the two numbers such that they add up to the target, where index1 must be less than index2. Please note that your returned answers (both index1 and index2)...