c*****m
发帖数: 271 | 1 别人分享的面经里面扩展的题，想不出O(N)的方法。请大牛们指点 | j*****8
发帖数: 3635 | 2 这个有啥tricky的地方吗，难道不是加个condition check currSum >= target 就行？
【在 c*****m 的大作中提到】
: 别人分享的面经里面扩展的题，想不出O(N)的方法。请大牛们指点
| c*****m
发帖数: 271 | 3 curSum < target的时候怎么操作呢？
【在 j*****8 的大作中提到】
: 这个有啥tricky的地方吗，难道不是加个condition check currSum >= target 就行？
| j*****8
发帖数: 3635 | 4 继续加
if currSum < 0 then currSum = 0
else if currSum >= target && currSum > curMax then currMax = currSum
没仔细想，可能不对
【在 c*****m 的大作中提到】
: curSum < target的时候怎么操作呢？
| c*****m
发帖数: 271 | 5 没错。我自己把问题想错了，之前脑子里面想的是找出 >= target的所有contiguous
subarray里面长度最大的那个.
【在 j*****8 的大作中提到】
: 继续加
: if currSum < 0 then currSum = 0
: else if currSum >= target && currSum > curMax then currMax = currSum
: 没仔细想，可能不对
| j*****8
发帖数: 3635 | 6 那个也一样吧，只是不记录currMaxSum，而是currMaxLength
contiguous
【在 c*****m 的大作中提到】
: 没错。我自己把问题想错了，之前脑子里面想的是找出 >= target的所有contiguous
: subarray里面长度最大的那个.
| c*****m
发帖数: 271 | 7 这种情况的话，在curSum < target时，不能把curSum重置０吧？比如target = 10,
array=[-1, 100]，最大长度是２，而不是１
【在 j*****8 的大作中提到】
: 那个也一样吧，只是不记录currMaxSum，而是currMaxLength
:
: contiguous
| j*****8
发帖数: 3635 | 8 en，你是对的
那就得用求subarray sum来做了
【在 c*****m 的大作中提到】
: 这种情况的话，在curSum < target时，不能把curSum重置０吧？比如target = 10,
: array=[-1, 100]，最大长度是２，而不是１
| c*****m
发帖数: 271 | 9 和暴力的方法的复杂度都是O(N^2)的吧？
【在 j*****8 的大作中提到】
: en，你是对的
: 那就得用求subarray sum来做了
| j*****8
发帖数: 3635 | 10 好像是。。
【在 c*****m 的大作中提到】
: 和暴力的方法的复杂度都是O(N^2)的吧？
| | | r*******g
发帖数: 1335 | 11 https://en.wikipedia.org/wiki/Maximum_subarray_problem
【在 c*****m 的大作中提到】
: 别人分享的面经里面扩展的题，想不出O(N)的方法。请大牛们指点
| b*****n
发帖数: 618 | 12 如果是求最长的subarray的话，用TreeMap可以O(nlogn)，
谨慎地认为没有更好的解了。。 | i******l
发帖数: 270 | 13 我想到了一个办法，刚刚试了一下，确实是O(N)的。
思路就是从两头往中间凑，先得到全部的和，如果满足条件就返回了，
如果不满足，比较两头的大小，每次减去小的那个，然后走一步，代码如下：
int maxSubLen( vector& data, int bar ) {
int sz = data.size(), sum = 0;
for( int i=0; i
if( sum >= bar ) return sz;
int i = 0, j = sz-1;
while( i < j ) {
if( data[i] < data[j] ) sum -= data[i++];
else sum -= data[j--];
if( sum >= bar ) return j - i + 1;
}
return 0;
}
int main() {
vector v {-1,-1,-1,2,-1,-1,100};
vector v2 {1,-1,-1,1,-1,-1,1,-1,-2,7};
vector v3 {-1,-1,-1,2,-1,-1,1};
cout<
cout<
cout<
}
都在刷题奋力找工作中，共勉
【在 c*****m 的大作中提到】
: 别人分享的面经里面扩展的题，想不出O(N)的方法。请大牛们指点
| a********g
发帖数: 36 | 14 有个反例子：｛1，1，1，1，1，-9，7｝，target:5
正确的答案是1，1，1，1，1长度是5
而你的解法的答案是7，长度只有1
【在 i******l 的大作中提到】
: 我想到了一个办法，刚刚试了一下，确实是O(N)的。
: 思路就是从两头往中间凑，先得到全部的和，如果满足条件就返回了，
: 如果不满足，比较两头的大小，每次减去小的那个，然后走一步，代码如下：
: int maxSubLen( vector& data, int bar ) {
: int sz = data.size(), sum = 0;
: for( int i=0; i: if( sum >= bar ) return sz;
:
: int i = 0, j = sz-1;
: while( i < j ) {
| y*********e
发帖数: 518 | 15 如果array里面每一个数字都是正的话，那么有最优解时间O(N)，空间O(1)。用一个
slicing window就好。
若是有负的数字，没有O(N)时间的解答，最好的是O(NlogN)。
【在 c*****m 的大作中提到】
: 别人分享的面经里面扩展的题，想不出O(N)的方法。请大牛们指点
| b*****n
发帖数: 618 | 16 又想了一下，其实是有O(N)的解的。
先precompute sum array，b[x] = sum(a[0] + a[1] + ... + a[x])
然后问题相当于在b里面找两个个index i，j, i在左边j在右边， b[j] - b[i] >= tar
，并且要j - i的值最大。
所有可能作为i的candidate实际上只有从b[0]开始向右的严格递减subsequence，
因为假如x > y并且b[x] > b[y]的话，那么x不可能作为i，因为y作为i更好。
同样，所有可能作为j的candidate实际上只有从b[n]开始向左的严格递增subsequence。
举个例子，如果b = [5, 4, 2, 8, 3, 7]
那么i的可能其实只有index 0,1,2,
j的可能其实只有index 3,5
然后用两个pointer分别从这两个序列的尾部开始往前移动就可以了，时间复杂度整体
上是O(N)因为上面每一步都是O(N)
【在 y*********e 的大作中提到】
: 如果array里面每一个数字都是正的话，那么有最优解时间O(N)，空间O(1)。用一个
: slicing window就好。
: 若是有负的数字，没有O(N)时间的解答，最好的是O(NlogN)。
| y*********e
发帖数: 518 | 17
tar
subsequence。
举个例子：b = [1, 5, 9, 4, 2, 8, 3, 7, 9]
按照你的算法，如何求 i 和 j 呢？
【在 b*****n 的大作中提到】
: 又想了一下，其实是有O(N)的解的。
: 先precompute sum array，b[x] = sum(a[0] + a[1] + ... + a[x])
: 然后问题相当于在b里面找两个个index i，j, i在左边j在右边， b[j] - b[i] >= tar
: ，并且要j - i的值最大。
: 所有可能作为i的candidate实际上只有从b[0]开始向右的严格递减subsequence，
: 因为假如x > y并且b[x] > b[y]的话，那么x不可能作为i，因为y作为i更好。
: 同样，所有可能作为j的candidate实际上只有从b[n]开始向左的严格递增subsequence。
: 举个例子，如果b = [5, 4, 2, 8, 3, 7]
: 那么i的可能其实只有index 0,1,2,
: j的可能其实只有index 3,5
| b*****n
发帖数: 618 | 18 这种情况下i只可能是0，因为后面没有比1小的了
j只可能是8，因为前面没有比9大的了
这个array里面没有比9-1更好也更长的b[j] - b[i]了 | j*****8
发帖数: 3635 | 19 但如果当前 i, j 不满足条件并且 i 向右 j 向左 都可以时，先移动哪一个？
我把你的例子b稍微改了下 b = [6, 5,4,10,3,7], target = 4
i 还是可选 0,1,2；j 还是可选3，5
i = 0, j = 5 时不满足条件，这个时候先移 i 还是 j？ 感觉按你的算法应该先移 i
， 但那样就拿不到 i = 0 j = 3 的解了？
tar
subsequence。
【在 b*****n 的大作中提到】
: 又想了一下，其实是有O(N)的解的。
: 先precompute sum array，b[x] = sum(a[0] + a[1] + ... + a[x])
: 然后问题相当于在b里面找两个个index i，j, i在左边j在右边， b[j] - b[i] >= tar
: ，并且要j - i的值最大。
: 所有可能作为i的candidate实际上只有从b[0]开始向右的严格递减subsequence，
: 因为假如x > y并且b[x] > b[y]的话，那么x不可能作为i，因为y作为i更好。
: 同样，所有可能作为j的candidate实际上只有从b[n]开始向左的严格递增subsequence。
: 举个例子，如果b = [5, 4, 2, 8, 3, 7]
: 那么i的可能其实只有index 0,1,2,
: j的可能其实只有index 3,5
| b*****n
发帖数: 618 | 20 这个例子里面
i可以选 0，1，2，4
j可以选3，5
i和j都应该从最右边，也就是最大的index开始往左边走，跟sliding window的思路类
似，i开始是4，j开始是5，如果发现a[j] - a[i] >= tar就移动i，反之移动j，相当于
对每个可能的j求最小的i是多少
i
【在 j*****8 的大作中提到】
: 但如果当前 i, j 不满足条件并且 i 向右 j 向左 都可以时，先移动哪一个？
: 我把你的例子b稍微改了下 b = [6, 5,4,10,3,7], target = 4
: i 还是可选 0,1,2；j 还是可选3，5
: i = 0, j = 5 时不满足条件，这个时候先移 i 还是 j？ 感觉按你的算法应该先移 i
: ， 但那样就拿不到 i = 0 j = 3 的解了？
:
: tar
: subsequence。
| | | j*****8
发帖数: 3635 | 21
~~~~~~~~~~~~~~~~~~~~~
那时间复杂度就不是线性的了。可能都从右开始能解
决这个例子，但我总觉得还会有别的反例，虽然现在没想出来。。
【在 b*****n 的大作中提到】
: 这个例子里面
: i可以选 0，1，2，4
: j可以选3，5
: i和j都应该从最右边，也就是最大的index开始往左边走，跟sliding window的思路类
: 似，i开始是4，j开始是5，如果发现a[j] - a[i] >= tar就移动i，反之移动j，相当于
: 对每个可能的j求最小的i是多少
:
: i
| b*****n
发帖数: 618 | 22 仍然是线性的，i和j都最多有n个，每一步要么i往坐移要么j往坐移，最多O(2n)。
反例应该是没有的，利用的就是两个sequence其实都是从左往右递增的序列。
【在 j*****8 的大作中提到】
:
: ~~~~~~~~~~~~~~~~~~~~~
: 那时间复杂度就不是线性的了。可能都从右开始能解
: 决这个例子，但我总觉得还会有别的反例，虽然现在没想出来。。
| r****7
发帖数: 2282 | 23 这个不是lc上的原题么？
【在 c*****m 的大作中提到】
: 别人分享的面经里面扩展的题，想不出O(N)的方法。请大牛们指点
| b***e
发帖数: 1419 | 24 我认为是有O(n)的解的。
第一步，先计算从所有位置开始的max sum。这是标准的dp解法。记这个结果array为M[
i]。
第二步，找到从左往右第一个i，使得M[i] >= target。
第三步，从i开始从左往右找第一个j，使得sum[i..j] >= target，并且sum[i..j] + M
[j+1] < target。这是找到了从左往右第一个最长的合法子序列。
第四步，向右挪i，直到(a) i >= j或者(b)sum[i..j] + M[j+1] >= target。如果(a)
发生了，goto第二步。如果(a)没发生但是(b)发生了，goto第三步。
算法描述不是结构化的。但是应该是O(n)的。因为i和j都是从左往右扫描了一遍。
【在 y*********e 的大作中提到】
: 如果array里面每一个数字都是正的话，那么有最优解时间O(N)，空间O(1)。用一个
: slicing window就好。
: 若是有负的数字，没有O(N)时间的解答，最好的是O(NlogN)。
|
|
