Leetcode 689居然是fb的高频题？ - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>JobHunting - 待字闺中

Leetcode 689居然是fb的高频题？

Leetcode 689居然是fb的高频题？# JobHunting - 待字闺中

s*b2017-10-30 07:10

1 楼

Maximum Sum of 3 Non-Overlapping Subarrays。
看了半天，答案也看的不是很懂。
这道居然会是高频题？

u*u2017-10-30 07:10

2 楼

可能因为思路简单吧

w*o2017-10-30 07:10

3 楼

叔这个题目是动态编程。
其实不是很复杂。
1. 就是你先算一下以k为长度，滑动窗口的和，放到一个数组里。
2. 从左到右计算以i为起点，到i为止，最大值的窗口的起始index
比如说[1,3,2,0]
所对应[0,1,1] 因为 2 + 0 < 3 + 2
3.从右向左计算以z为为起点，从z向右考虑，最大窗口和的起始index
4.因为窗口不能重复，所以i + k <= j + k <= z
在j的范围内遍历并且更新结果就可以了。
代码如下：
class Solution {
public int[] maxSumOfThreeSubarrays(int[] nums, int k) {
int sum = 0, len = nums.length - k + 1;
int[] sums = new int[len];
for (int i = 0; i < nums.length; i++) {
sum += nums[i];
if (i >= k) sum -= nums[i - k];
if (i >= k - 1) sums[i - k + 1] = sum;
}

int[] left = new int[len];
int best = 0;
for (int i = 0; i < len; i++) {
if (sums[i] > sums[best]) best = i;
left[i] = best;
}

int[] right = new int[len];
best = len - 1;
for (int i = len - 1; i >= 0; i--) {
if (sums[i] >= sums[best]) best = i;
right[i] = best;
}

int[] res = {0, k, 2 * k};
for (int j = k; j < len - k; j++) {
int i = left[j - k], z = right[j + k];
if (sums[i] + sums[j] + sums[z] > sums[res[0]] + sums[res[1]] +
sums[res[2]]) {
res[0] = i;
res[1] = j;
res[2] = z;
}
}
return res;
}
}

s*b2017-10-30 07:10

4 楼

赞，太厉害了

【在 w*******o 的大作中提到】

: 叔这个题目是动态编程。
: 其实不是很复杂。
: 1. 就是你先算一下以k为长度，滑动窗口的和，放到一个数组里。
: 2. 从左到右计算以i为起点，到i为止，最大值的窗口的起始index
: 比如说[1,3,2,0]
: 所对应[0,1,1] 因为 2 + 0 < 3 + 2
: 3.从右向左计算以z为为起点，从z向右考虑，最大窗口和的起始index
: 4.因为窗口不能重复，所以i + k <= j + k <= z
: 在j的范围内遍历并且更新结果就可以了。
: 代码如下：