avatar
S*w
2
Leetcode原题,three sum的变种, 容许数字重用
avatar
d*u
3
不是100% 肯定
avatar
r*g
4
?

【在 S***w 的大作中提到】
: Leetcode原题,three sum的变种, 容许数字重用
avatar
b*5
5
我靠, 我估计就挂在了这题。。
就是比如 【-2, -1, 0, 0 , 1, 1, 2】
this is corresponding to [ a, b, c, d, e, f, g]
比如说你要的target是0
要的答案是: 【b, c, e] ( first 0, first 1)
[b, c, f] (first 0, second 1)
[b, d, e] (second 0, first 1)
[b, d, f] (second 0, second 1)
along with others...


【在 S***w 的大作中提到】
: Leetcode原题,three sum的变种, 容许数字重用
avatar
y*e
8
那可不一定。。。没有拒信就有希望!

【在 b**********5 的大作中提到】
: 我靠, 我估计就挂在了这题。。
: 就是比如 【-2, -1, 0, 0 , 1, 1, 2】
: this is corresponding to [ a, b, c, d, e, f, g]
: 比如说你要的target是0
: 要的答案是: 【b, c, e] ( first 0, first 1)
: [b, c, f] (first 0, second 1)
: [b, d, e] (second 0, first 1)
: [b, d, f] (second 0, second 1)
: along with others...
:

avatar
S*w
9
谢谢 大家回复
这题目就是看着简单 其实不简单
avatar
S*w
10
是不是考虑用 combinational sum 方法
avatar
g*c
11
这题是不是用backtracking?
avatar
b*5
12
我被问的题, 是只能取3个element

【在 S***w 的大作中提到】
: 是不是考虑用 combinational sum 方法
avatar
S*w
13
请 斧正 感觉有点over kill
public List> findSum(int[] candidates, int k, int target) {
List> ret = new ArrayList>();
if (candidates.length == 0) return ret;
Arrays.sort(candidates);
List path = new ArrayList();
dfs(candidates, 0, k, target, path, ret);
return ret;
}
private void dfs(int[] candidates, int depth, int k, int target, List<
Integer> path, List> ret) {
if (k == path.size()) {
if (target == 0) ret.add(new ArrayList(path));
}
else {
if (target < 0 || depth == candidates.length || target <
candidates[depth]) {
return;
}
else {
for(int i = depth; i < candidates.length; ++i) {
path.add(i);
dfs(candidates, i, k, target - candidates[i], path, ret);
path.remove(path.size() - 1);
}
}
}
}
{-2, -1, 0, 0, 1, 1, 1, 2}
0 1 2 3 4 5 6 7
[0, 2, 7]
[0, 3, 7]
[0, 4, 4]
[0, 4, 5]
[0, 4, 6]
[0, 5, 5]
[0, 5, 6]
[0, 6, 6]
[1, 1, 7]
[1, 2, 4]
[1, 2, 5]
[1, 2, 6]
[1, 3, 4]
[1, 3, 5]
[1, 3, 6]
[2, 2, 2]
[2, 2, 3]
[2, 3, 3]
[3, 3, 3]
-2, 0, 1, 2, 4, 6
0 1 2 3 4 5
是说比如-2,4,6,1,2,0取三数和为0的话,那么
-2,-2,4
-2,2,0
-2,1,1
0,0,0
[0, 0, 4] -2, -2, 4
[0, 1, 3] -2, 0, 2
[0, 2, 2] -2, 1, 1
[1, 1, 1] 0, 0, 0
avatar
S*w
14
是的, 可以只检查选择3个情况

【在 b**********5 的大作中提到】
: 我被问的题, 是只能取3个element
avatar
p*g
15
这个复杂度是O(n^k)

) {

【在 S***w 的大作中提到】
: 请 斧正 感觉有点over kill
: public List> findSum(int[] candidates, int k, int target) {
: List> ret = new ArrayList>();
: if (candidates.length == 0) return ret;
: Arrays.sort(candidates);
: List path = new ArrayList();
: dfs(candidates, 0, k, target, path, ret);
: return ret;
: }
: private void dfs(int[] candidates, int depth, int k, int target, List<

avatar
b*5
16
我用的是3sum的两个index的变形, 就是等于target的时候, 我写的乱七八糟的。。
其实还没combination sum清楚。。。

【在 S***w 的大作中提到】
: 是的, 可以只检查选择3个情况
avatar
S*w
17
也不算吧
C(N,3) N^3

【在 p*********g 的大作中提到】
: 这个复杂度是O(n^k)
:
: ) {

avatar
S*w
18
所以感觉有点overkill
来这里问问



【在 b**********5 的大作中提到】
: 我用的是3sum的两个index的变形, 就是等于target的时候, 我写的乱七八糟的。。
: 其实还没combination sum清楚。。。

avatar
b*5
19
对。 我后来写的3sum的变形, 也变为N^3了, 所以我觉得他虽然说3sum,其实就是
考combination sum

【在 S***w 的大作中提到】
: 也不算吧
: C(N,3) N^3

avatar
S*w
20
用3sum的话
固定i,
如果 Ai + Aj + Ak == target,
j, k 怎么移动?
++j, --k 肯定会漏掉
++j, 可能漏调 1, xxxx, -1, -1 的情况
---k 类似
总之不太好写

【在 b**********5 的大作中提到】
: 对。 我后来写的3sum的变形, 也变为N^3了, 所以我觉得他虽然说3sum,其实就是
: 考combination sum

avatar
b*5
21
我用了两个while loop, outer loop移动j, inner loop移动k。。。
所以写的磕磕碰碰的。。 所以我说combination sum写清楚。。。

【在 S***w 的大作中提到】
: 用3sum的话
: 固定i,
: 如果 Ai + Aj + Ak == target,
: j, k 怎么移动?
: ++j, --k 肯定会漏掉
: ++j, 可能漏调 1, xxxx, -1, -1 的情况
: ---k 类似
: 总之不太好写

avatar
r*7
22
这个不如排个序然后用2sum得两种解法相结合,N^2

【在 S***w 的大作中提到】
: 也不算吧
: C(N,3) N^3

avatar
b*5
23
你写个code出来看看。。。

【在 r****7 的大作中提到】
: 这个不如排个序然后用2sum得两种解法相结合,N^2
avatar
t*r
24
说个题外话,这种题用FP写容易很多
用IP写实属蛋疼
avatar
S*w
25
求算法

【在 r****7 的大作中提到】
: 这个不如排个序然后用2sum得两种解法相结合,N^2
avatar
r*7
26
如果我没理解错,就是一组数中有3个数x[i0], x[i1], x[i2]加起来等于target,然后
这个数组中的数有重复?
那你就对x每个元素都做target - x[i]然后再在数组里求x[i0] + x[i1]等于target -
x[i]不就行了吗?

【在 S***w 的大作中提到】
: 求算法
avatar
S*w
27
任何一个数,都可以重用
如果 数组是 【0, 0】
你的算法是怎么弄?

-

【在 r****7 的大作中提到】
: 如果我没理解错,就是一组数中有3个数x[i0], x[i1], x[i2]加起来等于target,然后
: 这个数组中的数有重复?
: 那你就对x每个元素都做target - x[i]然后再在数组里求x[i0] + x[i1]等于target -
: x[i]不就行了吗?

avatar
p*g
28
我贴一个吧,不过是输出数字值,不是下标的。 不知道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);
}
return res;
}

private static void addToLists(List> lists, int i, int j,
int count ){
for (int k=0; kList list = new ArrayList();
list.add(i);
list.add(j);
lists.add(list);
}
}

private static List> twoSum(int[] nums, int s, int target){
List> lists = new ArrayList>();
int i=s, j=nums.length-1;
while ( iint sum = nums[i]+nums[j];
if ( sum>target ){
j--;
} else if (sum < target ){
i++;
} else {
int count ;
if ( nums[i] != nums[j] ) {
int left = 1;
int right =1;
while ( nums[i] == nums[i+left] )
left++;
while ( nums[j] == nums[j-right] )
right++;
count = left *right;
addToLists(lists, nums[i], nums[j], count);
i+=left;
j=j-right+1;
} else {
int len = j-i+1;
count = len*(len-1)/2;
addToLists(lists, nums[i], nums[j], count);
break;
}
}
}

return lists;
}
public static void main(String[] args) {
// TODO Auto-generated method stub
// int[] nums={-2, -1, 0, 1 ,1 , 2, 3, 4};
// int[] nums={-2, -1, 0, 0 , 1, 1, 2};
int[] nums={-2, -1, 0, 0, 1, 1, 1, 2};

int target = 0;
List> res = Fb3Sum.threeSum(nums, target);
for (List list : res) {
for ( int i : list )
System.out.print(i+", ");
System.out.println();
}
}
}
avatar
r*7
29
已经贴上了

【在 p*********g 的大作中提到】
: 我贴一个吧,不过是输出数字值,不是下标的。 不知道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) {

avatar
r*7
30
我开始理解错了,以为是元素有重复
不过可以重用有啥影响呢?2sum那种两头夹的方法可以改成重用的吧,允许start ==
end即可,再不济把数组给double一下啊。。。

【在 S***w 的大作中提到】
: 任何一个数,都可以重用
: 如果 数组是 【0, 0】
: 你的算法是怎么弄?
:
: -

avatar
c*n
31
这个在leetcode 上discussion forum 那么多答案, 为什么还问?
Arrays.sort(A);
for(int i=0;iint newTarget = target - A[i];
// now use the O(N) 2-sum on a sorted array
int l = i+1; int h = size-1;
while(l < h) {
if (A[l] + A[h] == newTarget) print_out_result;
else
if (A[l]+ A[h] < newTarget) l++;
else h--;
}
}

【在 S***w 的大作中提到】
: 求算法
avatar
S*w
32
我贴一个吧,不过是输出数字值,不是下标的。 不知道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.addAll(lists);
}
return res;
}

private static void addToLists(List> lists, int i, int j,
int count ){
for (int k=0; kList list = new ArrayList();
list.add(i);
list.add(j);
lists.add(list);
}
}

private static List> twoSum(int[] nums, int s, int target){
List> lists = new ArrayList>();
int i=s, j=nums.length-1;
while ( iint sum = nums[i]+nums[j];
if ( sum>target ){
j--;
} else if (sum < target ){
i++;
} else {
int count ;
if ( nums[i] != nums[j] ) {
int left = 1;
int right =1;
while ( nums[i] == nums[i+left] )
left++;
while ( nums[j] == nums[j-right] )
right++;
count = left *right;
addToLists(lists, nums[i], nums[j], count);
这错了?
i+=left;
j=j-right+1;
} else {
int len = j-i+1;
count = len*(len-1)/2;
不一定吧
addToLists(lists, nums[i], nums[j], count);
break;
}
}
}

return lists;
}
public static void main(String[] args) {
// TODO Auto-generated method stub
// int[] nums={-2, -1, 0, 1 ,1 , 2, 3, 4};
// int[] nums={-2, -1, 0, 0 , 1, 1, 2};
int[] nums={-2, -1, 0, 0, 1, 1, 1, 2};

int target = 0;
List> res = Fb3Sum.threeSum(nums, target);
for (List list : res) {
for ( int i : list )
System.out.print(i+", ");
System.out.println();
}
}
}

【在 p*********g 的大作中提到】
: 我贴一个吧,不过是输出数字值,不是下标的。 不知道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) {

avatar
b*5
33
差不多那个意思。 所以说, 还是combination sum 清楚。。。

【在 p*********g 的大作中提到】
: 我贴一个吧,不过是输出数字值,不是下标的。 不知道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) {

avatar
S*w
34
这不对吧
题目要求 数可以重用

【在 c******n 的大作中提到】
: 这个在leetcode 上discussion forum 那么多答案, 为什么还问?
: Arrays.sort(A);
: for(int i=0;i: int newTarget = target - A[i];
: // now use the O(N) 2-sum on a sorted array
: int l = i+1; int h = size-1;
: while(l < h) {
: if (A[l] + A[h] == newTarget) print_out_result;
: else
: if (A[l]+ A[h] < newTarget) l++;

avatar
b*5
35
其实, 还不大能用count, 因为其实不是int【】, 而是一个custom class
class S{
int num;
string name;
}
要输出的是name的组合。

【在 S***w 的大作中提到】
: 我贴一个吧,不过是输出数字值,不是下标的。 不知道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 可以重用

avatar
c*n
36
哦,sorry, 我理解成“有重复数” 。。。
how about simply replicating the array 3 times?

【在 S***w 的大作中提到】
: 这不对吧
: 题目要求 数可以重用

avatar
s*h
37
可是事先算算每个元素重复的个数吗?
上面的例子 只需要看 【-2, -1, 0 , 1, 2】,用普通的3sum 得到[-1,0,1] 因
为 -1重复一遍,0重复两遍,1重复遍,所以要输出 [-1,0,1] 1*2*2=4次就可以了。

【在 b**********5 的大作中提到】
: 我靠, 我估计就挂在了这题。。
: 就是比如 【-2, -1, 0, 0 , 1, 1, 2】
: this is corresponding to [ a, b, c, d, e, f, g]
: 比如说你要的target是0
: 要的答案是: 【b, c, e] ( first 0, first 1)
: [b, c, f] (first 0, second 1)
: [b, d, e] (second 0, first 1)
: [b, d, f] (second 0, second 1)
: along with others...
:

avatar
b*5
38
好像不大对
就是给你一个array
[{0, "a"}, {0, "b"} ,{1, "c"}, {1, "d"}]
target是1
你要输出 “ac”, "ad", "bc", "bd"
avatar
b*5
39
好人做到底吧。 还被问了POI, 那个fbrefer给的link里的POI的presentation, 好
像面试官听都没听说过。。。 反正最后也答的不大好
avatar
b*5
40
可以, 但你看我前面说的, 其实不是一个integer array, 是个custom class array
, class里有一个string 和integer, 用integer来算3sum, 输出的要是那些
corresponding name
比如-1有“a", "b" "c", 你就要输出“axx", "bxx”, “cxx“

【在 s*******h 的大作中提到】
: 可是事先算算每个元素重复的个数吗?
: 上面的例子 只需要看 【-2, -1, 0 , 1, 2】,用普通的3sum 得到[-1,0,1] 因
: 为 -1重复一遍,0重复两遍,1重复遍,所以要输出 [-1,0,1] 1*2*2=4次就可以了。

avatar
s*h
41
那这样的话最坏的情况会有 O(N^3) 的可能性,所以就只能combination了。
avatar
b*5
42
我说了半天了, 觉得还是combination简单清楚。。。

【在 s*******h 的大作中提到】
: 那这样的话最坏的情况会有 O(N^3) 的可能性,所以就只能combination了。
相关阅读
logo
联系我们隐私协议©2024 redian.news
Redian新闻
Redian.news刊载任何文章,不代表同意其说法或描述,仅为提供更多信息,也不构成任何建议。文章信息的合法性及真实性由其作者负责,与Redian.news及其运营公司无关。欢迎投稿,如发现稿件侵权,或作者不愿在本网发表文章,请版权拥有者通知本网处理。