S***w
发帖数: 1014 | 1 Leetcode原题，three sum的变种, 容许数字重用 | r*g
发帖数: 186 | 2 ?
【在 S***w 的大作中提到】
: Leetcode原题，three sum的变种, 容许数字重用
| b**********5
发帖数: 7881 | 3 我靠， 我估计就挂在了这题。。
就是比如 【-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的变种, 容许数字重用
| y*****e
发帖数: 712 | | b**********5
发帖数: 7881 | 5 反正我被问的， 就是我楼上写的那个意思。。 我结果写的吭哧吭哧的。。。
【在 y*****e 的大作中提到】
: 我问过这题
: http://www.mitbbs.com/article_t/JobHunting/32899939.html
| y*****e
发帖数: 712 | 6 那可不一定。。。没有拒信就有希望！
【在 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...
:
| S***w
发帖数: 1014 | | S***w
发帖数: 1014 | 8 是不是考虑用 combinational sum 方法 | g*****c
发帖数: 106 | | b**********5
发帖数: 7881 | 10 我被问的题， 是只能取3个element
【在 S***w 的大作中提到】
: 是不是考虑用 combinational sum 方法
| | | S***w
发帖数: 1014 | 11 请 斧正 感觉有点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 | S***w
发帖数: 1014 | 12 是的， 可以只检查选择3个情况
【在 b**********5 的大作中提到】
: 我被问的题， 是只能取3个element
| p*********g
发帖数: 116 | 13 这个复杂度是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<
| b**********5
发帖数: 7881 | 14 我用的是3sum的两个index的变形， 就是等于target的时候， 我写的乱七八糟的。。
其实还没combination sum清楚。。。
【在 S***w 的大作中提到】
: 是的， 可以只检查选择3个情况
| S***w
发帖数: 1014 | 15 也不算吧
C(N,3) N^3
【在 p*********g 的大作中提到】
: 这个复杂度是O(n^k)
:
: ) {
| S***w
发帖数: 1014 | 16 所以感觉有点overkill
来这里问问
。
【在 b**********5 的大作中提到】
: 我用的是3sum的两个index的变形， 就是等于target的时候， 我写的乱七八糟的。。
: 其实还没combination sum清楚。。。
| b**********5
发帖数: 7881 | 17 对。 我后来写的3sum的变形， 也变为N^3了， 所以我觉得他虽然说3sum，其实就是
考combination sum
【在 S***w 的大作中提到】
: 也不算吧
: C(N,3) N^3
| S***w
发帖数: 1014 | 18 用3sum的话
固定i,
如果 Ai + Aj + Ak == target,
j, k 怎么移动？
++j, --k 肯定会漏掉
++j, 可能漏调 1, xxxx, -1, -1 的情况
---k 类似
总之不太好写
【在 b**********5 的大作中提到】
: 对。 我后来写的3sum的变形， 也变为N^3了， 所以我觉得他虽然说3sum，其实就是
: 考combination sum
| b**********5
发帖数: 7881 | 19 我用了两个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 类似
: 总之不太好写
| r****7
发帖数: 2282 | 20 这个不如排个序然后用2sum得两种解法相结合，N^2
【在 S***w 的大作中提到】
: 也不算吧
: C(N,3) N^3
| | | b**********5
发帖数: 7881 | 21 你写个code出来看看。。。
【在 r****7 的大作中提到】
: 这个不如排个序然后用2sum得两种解法相结合，N^2
| t*********r
发帖数: 387 | 22 说个题外话，这种题用FP写容易很多
用IP写实属蛋疼 | S***w
发帖数: 1014 | 23 求算法
【在 r****7 的大作中提到】
: 这个不如排个序然后用2sum得两种解法相结合，N^2
| r****7
发帖数: 2282 | 24 如果我没理解错，就是一组数中有3个数x[i0], x[i1], x[i2]加起来等于target，然后
这个数组中的数有重复？
那你就对x每个元素都做target - x[i]然后再在数组里求x[i0] + x[i1]等于target -
x[i]不就行了吗？
【在 S***w 的大作中提到】
: 求算法
| S***w
发帖数: 1014 | 25 任何一个数，都可以重用
如果 数组是 【0， 0】
你的算法是怎么弄？
-
【在 r****7 的大作中提到】
: 如果我没理解错，就是一组数中有3个数x[i0], x[i1], x[i2]加起来等于target，然后
: 这个数组中的数有重复？
: 那你就对x每个元素都做target - x[i]然后再在数组里求x[i0] + x[i1]等于target -
: x[i]不就行了吗？
| p*********g
发帖数: 116 | 26 我贴一个吧，不过是输出数字值，不是下标的。 不知道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; k
List 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 ( i
int 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();
}
}
} | r****7
发帖数: 2282 | 27 已经贴上了
【在 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) {
| r****7
发帖数: 2282 | 28 我开始理解错了，以为是元素有重复
不过可以重用有啥影响呢？2sum那种两头夹的方法可以改成重用的吧，允许start ==
end即可，再不济把数组给double一下啊。。。
【在 S***w 的大作中提到】
: 任何一个数，都可以重用
: 如果 数组是 【0， 0】
: 你的算法是怎么弄？
:
: -
| c******n
发帖数: 4965 | 29 这个在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++;
else h--;
}
}
【在 S***w 的大作中提到】
: 求算法
| S***w
发帖数: 1014 | 30 我贴一个吧，不过是输出数字值，不是下标的。 不知道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; k
List 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 ( i
int 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) {
| | | b**********5
发帖数: 7881 | 31 差不多那个意思。 所以说， 还是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) {
| S***w
发帖数: 1014 | 32 这不对吧
题目要求 数可以重用
【在 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++;
| b**********5
发帖数: 7881 | 33 其实， 还不大能用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 可以重用
| c******n
发帖数: 4965 | 34 哦，sorry, 我理解成“有重复数” 。。。
how about simply replicating the array 3 times?
【在 S***w 的大作中提到】
: 这不对吧
: 题目要求 数可以重用
| s*******h
发帖数: 105 | 35 可是事先算算每个元素重复的个数吗？
上面的例子 只需要看 【-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...
:
| b**********5
发帖数: 7881 | 36 好像不大对
就是给你一个array
[{0, "a"}, {0, "b"} ,{1, "c"}, {1, "d"}]
target是1
你要输出 “ac”， "ad", "bc", "bd" | b**********5
发帖数: 7881 | 37 好人做到底吧。 还被问了POI， 那个fbrefer给的link里的POI的presentation， 好
像面试官听都没听说过。。。 反正最后也答的不大好 | b**********5
发帖数: 7881 | 38 可以， 但你看我前面说的， 其实不是一个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次就可以了。
| s*******h
发帖数: 105 | 39 那这样的话最坏的情况会有 O(N^3) 的可能性，所以就只能combination了。 | b**********5
发帖数: 7881 | 40 我说了半天了， 觉得还是combination简单清楚。。。
【在 s*******h 的大作中提到】
: 那这样的话最坏的情况会有 O(N^3) 的可能性，所以就只能combination了。
|
|
