題目
核心思路
這道題應(yīng)該算是困難題目里比較簡(jiǎn)單的一道了，最關(guān)鍵的就是知道怎么優(yōu)化來(lái)提高效率蝉娜。首先給出一種暴力法，先窮舉出所有的可能扎唾，然后去發(fā)現(xiàn)可以優(yōu)化的地方召川。
暴力法
想要窮舉所有可能，對(duì)于題目中提到的3個(gè)子數(shù)組胸遇，顯然需要至少三層循環(huán)荧呐，我們?cè)O(shè)i , j , m分別表示三個(gè)子數(shù)組的結(jié)尾下標(biāo)(開(kāi)頭也相同)，那就需要三層循環(huán)來(lái)遍歷i , j , m纸镊，然后還要從這三個(gè)下標(biāo)分別向前求 k 個(gè)數(shù)的和倍阐，也就是說(shuō)總共需要四層循環(huán)，復(fù)雜度十分可怕薄腻，代碼就不給出了收捣。
優(yōu)化一
這是一種很常見(jiàn)的方法，就是求前綴和庵楷，通過(guò)前綴和來(lái)求子數(shù)組的和可以省去一層循環(huán)罢艾，即知道結(jié)尾下標(biāo)之后向前遍歷求和的過(guò)程楣颠。
代碼
class Solution {
public int[] maxSumOfThreeSubarrays(int[] nums, int k) {
int[] ans = new int[3];
int[] sum = new int[nums.length + 1];
for (int i = 0; i < nums.length; i++) {
//求前綴和
sum[i + 1] = sum[i] + nums[i];
}
for (int i = nums.length; i >= k; i--) {
//求長(zhǎng)度為k的子數(shù)組的間隔和
sum[i] = sum[i] - sum[i - k];
}
int maxSum = 0;
//遍歷
for (int i = k; i <= nums.length - 2 * k; i++) {
for (int j = i + k; j <= nums.length - k; j++) {
for (int m = j + k; m <= nums.length; m++) {
if (maxSum < sum[i] + sum[j] + sum[m]) {
maxSum = sum[i] + sum[j] + sum[m];
ans[0] = i - k;
ans[1] = j - k;
ans[2] = m - k;
}
}
}
}
return ans;
}
}
思路仍是暴力，但是通過(guò)求前綴和的預(yù)處理咐蚯，把最內(nèi)層的循環(huán)省掉童漩，提高一些效率。
優(yōu)化二
一種直觀的想法：如果只找數(shù)組中一個(gè)最大的數(shù)春锋，直接用一個(gè)變量遍歷一遍即可矫膨；那么如果i , j , m的下標(biāo)范圍是確定的，問(wèn)題就會(huì)變得同上邊的想法期奔，變得很簡(jiǎn)單侧馅。不過(guò)這道題要求的是長(zhǎng)度為k的子數(shù)組，范圍就是可變的了呐萌。但是如果固定中間位置的下標(biāo) j 馁痴，此時(shí)他前后兩個(gè)子數(shù)組 i , m的下標(biāo)就變成固定范圍了，固定范圍肯定就會(huì)有一個(gè)最大值(即最優(yōu)解)肺孤，問(wèn)題有局部最優(yōu)解罗晕，也就須要用到DP了。
所以我們使用一個(gè) left 數(shù)組保存第一個(gè)子數(shù)組的局部最優(yōu)解赠堵，用一個(gè) right 數(shù)組保存最后一個(gè)子數(shù)組的局部最優(yōu)解小渊，然后遍歷每一個(gè)可能中間下標(biāo) j，就可以求出最終答案茫叭，并且可以省去兩層循環(huán)酬屉，效率大大提高。
代碼
class Solution {
public int[] maxSumOfThreeSubarrays(int[] nums, int k) {
int[] ans = new int[3];
int[] sum = new int[nums.length + 1];// 長(zhǎng)度+1揍愁，sum[0] = 0方便求前綴和
int[] left = new int[nums.length + 1];// 長(zhǎng)度與sum一致方便運(yùn)算梆惯、理解
int[] right = new int[nums.length + 1];// 同上
// 求前綴和
for (int i = 0; i < nums.length; i++) {
sum[i + 1] = sum[i] + nums[i];
}
// 求間隔為k的和，從下標(biāo)k開(kāi)始求吗垮，以結(jié)尾為主
for (int i = nums.length; i >= k; i--) {
sum[i] = sum[i] - sum[i - k];
}
// 求從左邊開(kāi)始，和最大的值最早出現(xiàn)的下標(biāo)
int maxNum = 0;
int index = 0;
for (int i = k; i <= nums.length - k * 2; i++) {
if (maxNum >= sum[i]) {// >=號(hào)保證存儲(chǔ)的是最先出現(xiàn)的下標(biāo)
left[i] = index;
} else {
left[i] = i;
index = i;
maxNum = sum[i];
}
}
// 求從右邊開(kāi)始凹髓，和最大的值最早出現(xiàn)的下標(biāo)
maxNum = 0;
index = 0;
for (int i = nums.length; i >= k * 2; i--) {
if (maxNum > sum[i]) {// >號(hào)保證存儲(chǔ)的是最先出現(xiàn)的下標(biāo)
right[i] = index;
} else {
right[i] = i;
maxNum = sum[i];
index = i;
}
}
// 遍歷j可能的位置烁登，求出所有可能的最大值
maxNum = 0;
for (int i = k * 2; i <= nums.length - k; i++) {
if (maxNum < sum[i] + sum[left[i - k]] + sum[right[i + k]]) {
maxNum = sum[i] + sum[left[i - k]] + sum[right[i + k]];
ans[0] = left[i - k] - k;// - k由于求間隔和的時(shí)候，和是存儲(chǔ)在每個(gè)間隔最后一個(gè)元素的下標(biāo)
ans[1] = i - k;
ans[2] = right[i + k] - k;
}
}
return ans;
}
}
我這里將和數(shù)組蔚舀、left數(shù)組饵沧、right數(shù)組大小都設(shè)為 nums.length + 1，主要是為了方便運(yùn)算赌躺，也方便理解狼牺，實(shí)際上用到的大小只有 nums.length - k 罷了。如有內(nèi)容錯(cuò)誤的地方還請(qǐng)指出礼患，感謝相遇~
