【题目】
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
* 题目: 15.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含代码
Leetcode two sum java 解法
文档python数组双指针算法求和问题LeetCode2sum3sum4sum含代码提取方式是百度网盘分享地址
oj.leetcode题解, 2sum, 运用hashtable解决这到问题,时间复杂度O(N)
leetcode 2sum leetCode解决方案 我对 leetCode 问题的解决方案 已解决的练习列表: 简单的: 2sum - 带有未排序的数组; O(n) 复杂度; 花了~3ms 2sum - 使用排序数组; O(n) 复杂度 罗马转整数; O(n) 复杂度 合并...
leetcode 2sum # Programming-Problems This will have many problems from all over the web, As of writing this readme there is Haskell 99: 28 finished + Huffman Coding LeetCode: LC1: 2Sum [Easy] LC2: Add...
leetcode 2sum 2总和 力码研究1
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...
3sum 力码 力扣算法 (注:“ :locked: " 表示你需要来自 Leetcode) # 标题 解决方案 困难 001 简单的 002 中等的 003 中等的 004 难的 005 中等的 006 简单的 007 简单的 008 简单的 009 简单的 010 难的 011 中等...
3sum leetcode-curation-topical 精选 Leetcode 问题,按主题/概念分类。 我的策展标准是问题必须是有价值的,而不仅仅是为了难而难。 有价值的问题通常可以以不同的时间/空间效率(通过使用各种数据结构)以多种...
主要介绍了LeetCode -- Path Sum III分析及实现方法的相关资料,希望通过本文能帮助到大家,需要的朋友可以参考下
刷LeetCode刷LeetCode刷LeetCode刷LeetCode刷LeetCode
答案LeetCode_1_TwoSum LeetCode 问题:给定一个整数数组,找出两个数字,使它们相加为特定的目标数字。 函数 twoSum 应该返回两个数字的索引,使它们相加为目标,其中 index1 必须小于 index2。 请注意,您返回的...
leetcode 轮廓 1_count_and_say.cpp - super_ugly_number.cpp - Detect_Pattern.cpp - degree_of_array.cpp - 键盘.cpp - 2Sum_Data_Structure_Design.cpp - shuffle_array.cpp - permutations.cpp - kth_missing_...
第 338 章力码 LeetCode刷题总结 1.Two Sum 2.Add Two Numbers 3.Longest Substring Without ...15.3Sum 16.3Sum Closest 17.Letter Combinations of a Phone Number 18.4Sum 19.Remove Nth Node From End
leetcode 2 sum c JS 算法与数据结构(LEETCODE) 环境安装 安装依赖 npm install --save-dev jest //单元测试 npm install babel-jest babel-core@^7.0.0-bridge.0 @babel/core regenerator-runtime babel-preset-env...
leetcode 2 sum c leetcode 力扣(Leetcode)编程题,JavaScript版本。 编号 中文题目 英文题目 题目描述 JavaScript 难度 1 Two Sum 简单 2 Add Two Numbers 中等 3 Longest Substring Without Repeating... 中等 5...
leetcode。 3sum leetcode-练习 算法实践 15. 3和 给定一个由 n 个整数组成的数组 nums,nums 中是否有元素 a、b、c 使得 a + b + c = 0? 在数组中找到所有唯一的三元组,其总和为零。 示例输入: [-1, 0, 1, 2, -1...
大佬的leetcode刷题笔记(c++版本)
leetcode 3sum nlogn LeetCode 刷LeetCode题目思路 1.经典题目2SUM,利用hash_map完成 已知俩数之和,求能组成这个和的数字在数组中的下标 以数组中的值为key value,下标为value,即能实现常数级的复杂度 2.3Sum ...