g**G
发帖数: 767 | 1 Did you consider to skip duplicate element?
I pasted my solution as follows, hope it helps
public ArrayList> threeSum(int[] num) {
ArrayList> threeSum = new ArrayList
Integer>>();
if (num == null || num.length == 0)
return threeSum;
Arrays.sort(num);
int len = num.length;
int prev1 = Integer.MIN_VALUE;
int prev2 = Integer.MIN_VALUE;
int prev3 = Integer.MIN_VALUE;
for (... 阅读全帖 |
|
A*******e
发帖数: 2419 | 2 不可能吧。这个python版都要20行了。
2/3/4-sum实际每个都有三个版本：
判断有没有解，只需找一组。
找所有唯一解
找所有解。
看了一下，我的版本比较长，是因为找所有解，LC只需要所有唯一解，这样可简化一些。
class Solution:
# @return a list of lists of length 3, [[val1,val2,val3]]
def threeSum(self, num):
num.sort()
result = []
for i in range(len(num)):
twoSumTuples = self.twoSum(num[i+1:], 0 - num[i])
if twoSumTuples:
for pair in twoSumTuples:
threeSum = [num[i]] + pair
if threeS... 阅读全帖 |
|
g******n
发帖数: 10 | 3 这题可以在循环内手动去重，也可以把 triplets 存到 hash set 里自动去重，函数返
回时再转回 list。前者代码略显啰嗦但时间复杂度最坏是 O(n^2)，后者代码更简洁但
时间复杂度更高，平均情况 O(n^2)，最坏情况 O(n^4)（例如共有 O(n^2) 个
triplets，全部被 hash 到同一个 bucket，每次插入都是 O(n^2)，所以总的时间复杂
度是 O(n^4)）。C++ 可以用 hash set 也可以先统一把 triplets 存到 vector<
vector> 里，然后 sort + unique + erase / resize 搞定。但是 C++ 这两种方
法都会超时，必须手动去重，Java 和 Python 用 hash set 都能过 OJ。
--------------------------------------------------------------------------
Java 版代码如下：
public class Solution {
public List>... 阅读全帖 |
|
p*********g
发帖数: 116 | 4 我贴一个吧，不过是输出数字值，不是下标的。 不知道fb要求什么。
import java.util.*;
public class Fb3Sum {
public static List> threeSum(int[] nums, int target) {
Arrays.sort(nums);
List> res = new ArrayList>();
for (int i=0; i<=nums.length-3; i++){
List> lists = twoSum(nums, i+1, target-nums[i]);
for (List list: lists) {
list.add(0, nums[i]);
}
res.addAll(lists);
... 阅读全帖 |
|
S***w
发帖数: 1014 | 5 我贴一个吧，不过是输出数字值，不是下标的。 不知道fb要求什么。
import java.util.*;
public class Fb3Sum {
public static List> threeSum(int[] nums, int target) {
Arrays.sort(nums);
List> res = new ArrayList>();
for (int i=0; i<=nums.length-3; i++){
List> lists = twoSum(nums, i+1, target-nums[i]);
// i 可以重用
for (List list: lists) {
list.add(0, nums[i]);
}
res... 阅读全帖 |
|
|
P*******b
发帖数: 1001 | 7 thanks,
是这样吗？
bool ThreeSum(vector nums)
{
std::sort(nums.begin(), nums.end());
for (size_t i = 0; i < nums.size(); i++)
{
size_t j = 0;
size_t k = nums.size() - 1;
while ( j < k )
{
int result = nums[j] + nums[k] - nums[i];
if ( (result < 0) || (i == j) )
j++;
else if ( (result > 0) || (i == k) )
k--;
else
return true;
}
}
return false; |
|
m***n
发帖数: 2154 | 8 找到问题了，确实有情况没考虑到。现在的代码还是不行，崩溃啊。。
import java.util.*;
public class Solution {
public ArrayList> threeSum(int[] num) {
// Start typing your Java solution below
// DO NOT write main() function
if(num==null || num.length==0) return null;
ArrayList> ret = new ArrayList>();
Arrays.sort(num);
int begin = 0;
int end = num.length-1;
for(int i=0;i阅读全帖 |
|
t**i
发帖数: 314 | 9 编译过了，运行出错，帮忙看看哪儿出了问题，多谢。
import java.util.*;
public class Solution {
public ArrayList> threeSum(int[] num) {
assert(num.length >= 3);
ArrayList> triplet = new
ArrayList>();
for(int i = 0; i < num.length - 2; i++) {
for(int j = i + 2; j < num.length; j++) {
for(int k = i + 1; k < j; k++) {
if((num[i] + num[j] + num[k]) == 0) {
int[] th... 阅读全帖 |
|
s*****9
发帖数: 93 | 10 用了DP，同时用了HashSet防止重复结果，运行时间无法通过Large Test. HashSet的查
找不是应该O(1)时间吗？怎样才能更快呢？请帮忙看一下：
import java.util.*;
public class Solution {
public ArrayList> threeSum(int[] num) {
HashSet> final_set = new HashSet
Integer>>();
ArrayList current_list = new ArrayList();
threeSumRecur(num, 0, current_list, final_set);
ArrayList> final_lists = new ArrayList
Integer>>();
... 阅读全帖 |
|
q****m
发帖数: 177 | 11 难道是因为用了 std::sort ?
class Solution {
public:
vector > threeSum(vector &num) {
vector > *set = new vector >;
vector a(num);
sort(a.begin(), a.end());
vector b(num);
for(int k = 0; k < a.size(); ++k)
{
int c = a[k];
for(int j = 0; j < b.size(); ++j)
{
b[j] = -c - a[j];
}
int i = 0;
int j = b.size() -1 ;
while(i < a.size() && j > -1)
... 阅读全帖 |
|
q****m
发帖数: 177 | 12 优化了以后，终于可以 pass large 了. 思路是先对 num 排序. 排序后 num[i] + num
[j] + num[k] = 0中只用考虑 i < j < k的情况
class Solution {
public:
vector > threeSum(vector &num) {
vector > *set = new vector >;
sort(num.begin(), num.end());
vector b;
b.reserve(num.size());
for(int k = 0; k < num.size(); ++k)
{
int c = num[k];
for(int j = 0; j < k; ++j)
{
b[j] = -c - num[j];
}
int i = 0;
... 阅读全帖 |
|
q****m
发帖数: 177 | 13 难道是因为用了 std::sort ?
class Solution {
public:
vector > threeSum(vector &num) {
vector > *set = new vector >;
vector a(num);
sort(a.begin(), a.end());
vector b(num);
for(int k = 0; k < a.size(); ++k)
{
int c = a[k];
for(int j = 0; j < b.size(); ++j)
{
b[j] = -c - a[j];
}
int i = 0;
int j = b.size() -1 ;
while(i < a.size() && j > -1)
... 阅读全帖 |
|
q****m
发帖数: 177 | 14 优化了以后，终于可以 pass large 了. 思路是先对 num 排序. 排序后 num[i] + num
[j] + num[k] = 0中只用考虑 i < j < k的情况
class Solution {
public:
vector > threeSum(vector &num) {
vector > *set = new vector >;
sort(num.begin(), num.end());
vector b;
b.reserve(num.size());
for(int k = 0; k < num.size(); ++k)
{
int c = num[k];
for(int j = 0; j < k; ++j)
{
b[j] = -c - num[j];
}
int i = 0;
... 阅读全帖 |
|
Z***A
发帖数: 33 | 15 写了3sum的solution，但是没通过OJ large judge，Run Status: Time Limit
Exceeded，请分析一下原因。
下面是code：
public ArrayList> threeSum(int[] num) {
// Start typing your Java solution below
// DO NOT write main() function
if (num.length < 3)
return new ArrayList>();
Arrays.sort(num);
ArrayList> res = new ArrayList
>();
for (int i=0; i < num.length; i++)
{
... 阅读全帖 |
|
Z***A
发帖数: 33 | 16 java用的不好见笑了，但是leetcode要求的返回类型就是ArrayList
Integer>>
public class Solution {
public ArrayList> threeSum(int[] num) {
// Start typing your Java solution below
// DO NOT write main() function
}
} |
|
s*******y
发帖数: 105 | 17 在leetcode网上看到一种解法，感觉是对的，但是通不过OJ，显示Time Limit
Exceeded， 懂的童鞋给分析下code哪里有问题,3ks~
class Solution {
public:
vector > threeSum(vector &num) {
// Start typing your C/C++ solution below
// Start typing your C/C++ solution below
// DO NOT write int main() function
sort(num.begin(),num.end());
vector > r;
vector a;
int len = num.size();
if( len < 3 || num[0] > 0 || num[len-1] < 0 )
{
retu... 阅读全帖 |
|
s*****n
发帖数: 994 | 18 用了unordered_map来check第三个数是否存在，如果unordered_map是O（1），那整个
算法复杂度是O（n＊n）啊，为什么过不了large test？
class Solution {
public:
vector > threeSum(vector &num) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
sort(num.begin(),num.end());
unordered_map m;
for (size_t i=0; i
m.insert (make_pair(num[i],true));
}
vector > solution_set;
for (... 阅读全帖 |
|
f*******w
发帖数: 1243 | 19 2轮一起，一人45分钟 总共2小时…
两个面试官都是白人
都是比较简单的问题，但答得也不算好…
第一个人问怎么reverse一个singly linked list，和怎么implement circular queue
code倒是写出来了，不过bug不少，毕竟平时练得太少，不过磕磕碰碰还是改对了
第二个问了一些简历上的问题
然后问Top K问题，但是不要算法思路，是问我有没有在linux上做过，可以直接用什么
命令来实现
我说不知道，但是还是把思路解释了……
算法题都不难，一个是reverse C-style string，一个是two sum。twosum用hashtable
的话怎么处理重复，我说加上counter；然后twosum之后怎么做threesum，复杂度等等。
现在想起来感觉蛮简单的，不过还是……
Whatever |
|
f*******w
发帖数: 1243 | 20 2轮一起，一人45分钟 总共2小时…
两个面试官都是白人
都是比较简单的问题，但答得也不算好…
第一个人问怎么reverse一个singly linked list，和怎么implement circular queue
code倒是写出来了，不过bug不少，毕竟平时练得太少，不过磕磕碰碰还是改对了
第二个问了一些简历上的问题
然后问Top K问题，但是不要算法思路，是问我有没有在linux上做过，可以直接用什么
命令来实现
我说不知道，但是还是把思路解释了……
算法题都不难，一个是reverse C-style string，一个是two sum。twosum用hashtable
的话怎么处理重复，我说加上counter；然后twosum之后怎么做threesum，复杂度等等。
现在想起来感觉蛮简单的，不过还是……
Whatever |
|
x*****0
发帖数: 452 | 21 遇到一个奇怪的问题。对于同样的数据集，在自己的IDE上测试，没有任何问题，
leetcode的onlinejudge却报错。
例如：
leetcode online judge
input output expected
[0,0] [[0,0,0]] []
[1,2,-2,-1] [[-2,2,0],[-1,1,0]] []
[-1,0,1,2,-1,-4] [[-1,1,0]] [[-1,-1,2],[-1,0,1]]
在自己的IDE上，能够给出expected的答案。
下面是我的代码：
class Solution {
public:
vector > threeSum(vector &num) {
// Start typing your C/C++ solution below
// DO NO... 阅读全帖 |
|
g********E
发帖数: 178 | 22 1，第一层循环的时候跳过重复的；
2，第二层循环从两头跳过循环的；
vector< vector > threeSum(vector &num){
int n = num.size();
vector< vector > res;
vector cur;
sort(num.begin(), num.end());
for(int i = 0; i < n-2; i++){
if(i > 0 && num[i] == num[i-1]) continue;
cur.push_back(num[i]);
int start = i + 1, end = n - 1;
while(start < end){
if(start > i+1 && num[start] == num[start-1]) {
start++; continue;
... 阅读全帖 |
|
j**7
发帖数: 143 | 23 public ArrayList> threeSum(int[] numbers) {
Arrays.sort(numbers);
ArrayList> list = new ArrayList
>>();
for (int i = 0; i < numbers.length; i++) {
if (i > 0 && numbers[i] == numbers[i - 1]) {
continue;
}
twoSumWhile(numbers, 0 - numbers[i], i + 1, list);
}
return list;
}
public void twoSumWhile(int[] numbers, int target, int start, ArrayList<... 阅读全帖 |
|
d******l
发帖数: 175 | 24 大家好，我纠结这道题目一些时间了。期间用Java写了3个算法，在Judge Large的时候
都说超时。请教高人帮忙分析一下我的一个算法的复杂度（基于TwoSum的一个解法）。
非常感谢。
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.HashMap;
import java.util.Map;
public class Solution {
public ArrayList> twoSum(int[] numbers, int target) {
ArrayList> twoSumList = new ArrayList
Integer>>();
Map map = new HashMap();
for (in... 阅读全帖 |
|
t**********r
发帖数: 2153 | 25 这个是过了OJ的code.为了不超时,加了点tweak.看起来没有以前那么好看了.
public static ArrayList> threeSum(int[] inputs) {
if (inputs == null || inputs.length <= 2) {
// throw new IllegalArgumentException("Invalid inputs");
return new ArrayList>();
}
Arrays.sort(inputs);
Set> matchedTriplets = new HashSet
Integer>>();
for (int i = 0; i < inputs.length - 2; i++) {
if (inputs[i] > 0... 阅读全帖 |
|
h*****7
发帖数: 60 | 26 不光是这道题，还有一些别的题python过不了。不才解法如下，之前写的一个不用查
list的版本也没过。
另外貌似像import sys; min = sys.maxint 这种都编译不过去？
class Solution:
# @return a list of lists of length 3, [[val1,val2,val3]]
def threeSum(self, num):
num.sort()
n = len(num)
res= []
if n<3:
return res
for i in range(n-2):
k = i + 1
j = n - 1
while k < j:
sum = num[i] + num[j] + num[k]
if sum < 0:
k += 1
... 阅读全帖 |
|
h*****7
发帖数: 60 | 27 试了 也过不了 如下：
class Solution:
# @return a list of lists of length 3, [[val1,val2,val3]]
def threeSum(self, num):
num.sort()
n = len(num)
res= []
if n<3:
return res
for i in range(n-2):
j = n-1
if i > 0 and num[i] == num[i-1]:
continue
k = i + 1
while k < j:
sum = num[i] + num[j] + num[k]
if sum < 0:
k += 1
el... 阅读全帖 |
|
k*******3
发帖数: 2 | 28 class Solution:
# @return a list of lists of length 3, [[val1,val2,val3]]
def threeSum(self, num):
if len(num) < 3:
return []
num.sort()
final_results = []
for i in range(len(num)-2):
if i == 0 or num[i] > num[i-1]:
first = num[i]
sum_of_two = 0 - first
left_index = i + 1
right_index = len(num) - 1
while left_index < right_index:
tmp_... 阅读全帖 |
|
a***e
发帖数: 413 | 29 请问大牛，这两道题在skip 相同元素的时候，为什么要用类似
if(x < num.size()-1 & num[x] == num[x+1]) continue; // Skip same
x
而不是 // if( num[x] == num[x-1]) continue;
我自己写的时候是comment out的语句，但总是出错。没搞懂为啥
3sum的代码如下。非常感谢！
vector > threeSum(vector &num) {
vector> result;
sort(num.begin(), num.end());
for (int x = num.size()-1; x >=2; x--) { // Do it backwards
if(x < num.size()-1 & num[x] == num[x+1]) continue; // Skip same
x
// if( num... 阅读全帖 |
|
G***n
发帖数: 877 | 30 总是有Output Limit Exceeded的error怎么回事？
class Solution {
public:
vector > threeSum(vector &num) {
vector> list;
if (num.size() <= 2) return list;
sort(num.begin(), num.end());
for (int i = 0; i
{
int j = i+1, k=num.size()-1;
while (j
{
int t = num[i]+num[j]+num[k];
if (t == 0)
{
... 阅读全帖 |
|
w********n
发帖数: 4752 | 31 class Solution:
# @return a list of lists of length 3, [[val1,val2,val3]]
def threeSum(self, num):
size = len(num)
if size < 3:
return []
num.sort()
res = []
for i in range(size):
if i >0 and num[i] == num[i-1]:
continue
target = -num[i]
start = i+1
end = size - 1
while start < end:
if target == num[start] + num[end]:
res.appe... 阅读全帖 |
|
c**z
发帖数: 669 | 32 public class Solution {
public List> threeSum(int[] num) {
Arrays.sort(num);
List> ret = new ArrayList>();
for( int i=0 ;i
{
int j=i+1;
int k=num.length - 1;
while(j
{
int sum = num[i] + num[j] + num[k];
if ( sum == 0)
{
ArrayList temp = new ArrayList阅读全帖 |
|
t*****t
发帖数: 285 | 33 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.
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)
class Solution {
private:
int increment(vector& nums, int l, int r){
while(l阅读全帖 |
|
u**l
发帖数: 35 | 34 class Solution {
public:
vector> threeSum(vector& nums) {
vector> ret;
if (nums.size() < 3) {
return ret;
}
sort(nums.begin(), nums.end());
for (int i = 0; i < nums.size() - 2; ++i) {
if (i > 0 && nums.at(i) == nums.at(i - 1)) {
continue;
}
twoSum(ret, i + 1, nums, 0 - nums.at(i));
}
return ret;
}
private:
void twoSum(vector>... 阅读全帖 |
|
