e***s
发帖数: 799 | 1 之前大牛电面题，不知道有没有比O(n^2）快的答案？
Given a integer array, test if there is any consequence subarray
which sum of elements is 0.
[7, 1, 1, -2, 3, 4] ==> true [1, 1, -2] | s****g
发帖数: 43 | 2 Input S[N]. Make another array T, let T[i]=the sum of S[0] to S[i]: O(N).
Then sort T: O(NlgN). Walk through T again, if there are duplicates, then
there must exist a sum-0 sequence. | c*****e
发帖数: 59 | | c*******2
发帖数: 60 | 4 Beautiful !
Input S[N]. Make another array T, let T[i]=the sum of S[0] to S[i]: O(N).
Then sort T: O........
【在 s****g 的大作中提到】
: Input S[N]. Make another array T, let T[i]=the sum of S[0] to S[i]: O(N).
: Then sort T: O(NlgN). Walk through T again, if there are duplicates, then
: there must exist a sum-0 sequence.
| c*****e
发帖数: 59 | 5 Input [7, 1, 1, -2, 3, 4]
sort [-2, 1, 1, 3, 4, 7]
T [-2, -1, 0, 3, 7, 14] ?
but no duplicate ? | d****n
发帖数: 397 | 6 divide conqur?和mergesort一样nlogn?
有0就输出true,如果数组不含0，
首先讲数组分为两半
判断两半是不是有true,有的话，return true,否则从中间开始，
i=floor[n/2],j=ceiling[n/2],如果i--,j++,直到i=0,j=n-1还没有sum是0的情况，
return false.
这样
T(n)=2T(n/2)+theta(n)=theta(nlogn);
【在 e***s 的大作中提到】
: 之前大牛电面题，不知道有没有比O(n^2）快的答案？
: Given a integer array, test if there is any consequence subarray
: which sum of elements is 0.
: [7, 1, 1, -2, 3, 4] ==> true [1, 1, -2]
| y********9
发帖数: 130 | 7
你得排序和
【在 c*****e 的大作中提到】
: Input [7, 1, 1, -2, 3, 4]
: sort [-2, 1, 1, 3, 4, 7]
: T [-2, -1, 0, 3, 7, 14] ?
: but no duplicate ?
| s*w
发帖数: 729 | 8 use hash table to check duplicates, so it is O(N)
someone posted the code in the past few days
【在 s****g 的大作中提到】
: Input S[N]. Make another array T, let T[i]=the sum of S[0] to S[i]: O(N).
: Then sort T: O(NlgN). Walk through T again, if there are duplicates, then
: there must exist a sum-0 sequence.
| c*****e
发帖数: 59 | 9 OK，明白了，
除了验证duplicate，还需要验证 T 第三位是不是零这个特殊情况
【在 c*****e 的大作中提到】
: Input [7, 1, 1, -2, 3, 4]
: sort [-2, 1, 1, 3, 4, 7]
: T [-2, -1, 0, 3, 7, 14] ?
: but no duplicate ?
| e***s
发帖数: 799 | 10 牛！我必须声明，我在回复大牛之前自己想到了。
A = [7,1,1,-2,3,4]
S = [7,8,9,7,10,14]
S[0] == S[3]
所以return true, [A[1], A[2], A[3]]
【在 s****g 的大作中提到】
: Input S[N]. Make another array T, let T[i]=the sum of S[0] to S[i]: O(N).
: Then sort T: O(NlgN). Walk through T again, if there are duplicates, then
: there must exist a sum-0 sequence.
| p******s
发帖数: 40 | 11 应该不对，i--,j++如何协调？海猪的解法简单明了
【在 d****n 的大作中提到】
: divide conqur?和mergesort一样nlogn?
: 有0就输出true,如果数组不含0，
: 首先讲数组分为两半
: 判断两半是不是有true,有的话，return true,否则从中间开始，
: i=floor[n/2],j=ceiling[n/2],如果i--,j++,直到i=0,j=n-1还没有sum是0的情况，
: return false.
: 这样
: T(n)=2T(n/2)+theta(n)=theta(nlogn);
|
|
