難度：困難

給你一個(gè)整數(shù)數(shù)組 nums 和一個(gè)整數(shù) k ，找出三個(gè)長(zhǎng)度為 k 戳气、互不重疊、且 3 * k 項(xiàng)的和最大的子數(shù)組吸占，并返回這三個(gè)子數(shù)組晴叨。
以下標(biāo)的數(shù)組形式返回結(jié)果凿宾，數(shù)組中的每一項(xiàng)分別指示每個(gè)子數(shù)組的起始位置（下標(biāo)從 0 開(kāi)始）矾屯。如果有多個(gè)結(jié)果，返回字典序最小的一個(gè)初厚。
示例1：
　輸入：nums = [1,2,1,2,6,7,5,1], k = 2
　輸出：[0,3,5]
　解釋：子數(shù)組 [1, 2], [2, 6], [7, 5] 對(duì)應(yīng)的起始下標(biāo)為 [0, 3, 5]件蚕。
也可以取 [2, 1], 但是結(jié)果 [1, 3, 5] 在字典序上更大。
示例2：
　輸入：nums = [1,2,1,2,1,2,1,2,1], k = 2
　輸出：[0,2,4]
提示：
　· 1 <= nums.length <= 2 * 104
　· 1 <= nums[i] < 216
　· 1 <= k <= floor(nums.length / 3)

舉個(gè)例子产禾，假設(shè)nums = {1, 2, 3, 1, 2, 4, 3, 2, 2, 4, 3, 1, 2}排作，子序列長(zhǎng)度k = 3。使用三個(gè)滑動(dòng)窗口亚情，每個(gè)窗口的長(zhǎng)度為k = 3妄痪，每個(gè)窗口都用來(lái)框出一個(gè)子序列，要保證三個(gè)窗口不重疊楞件。

定義sum1衫生、sum2、sum3為三個(gè)串口內(nèi)的元素之和土浸，idx1罪针、idx2、idx3為三個(gè)窗口的最后一個(gè)元素的位置（至于為什么是最后一個(gè)不是第一個(gè)黄伊，我在后面會(huì)解釋）泪酱。下圖示意一下三個(gè)窗口的含義。

題目中要求我們找到三個(gè)子序列元素之和最大的位置还最，我們用max_sum123表示最大值墓阀。這時(shí)我們需要思考兩個(gè)主要問(wèn)題：

1. 一個(gè)窗口左右滑動(dòng)時(shí)，我們?nèi)绾慰焖偾笕∵@個(gè)窗口內(nèi)的所有元素和sum拓轻？
2. 如何通過(guò)滑動(dòng)這三個(gè)窗口找到max_sum123岂津？

下面逐個(gè)解決這兩個(gè)問(wèn)題。

1. 如何求窗口內(nèi)的所有元素之和

如下圖所示悦即，窗口位于一個(gè)位置吮成，我們計(jì)算得到它的元素之和sum。

我們將窗口向右滑動(dòng)一下辜梳，計(jì)算新的sum值粱甫。我們并不需要將窗口內(nèi)所有的元素累加起來(lái)，這樣會(huì)做很多重復(fù)計(jì)算作瞄。我們只需要在前一次sum的基礎(chǔ)上茶宵，減去左邊離開(kāi)窗口的元素的值，再加上右邊新加入窗口的元素的值宗挥。這樣乌庶，窗口的前后兩個(gè)位置都包含的元素之和种蝶，就不需要再重復(fù)計(jì)算了。

注意瞒大，由于本例中由于k=3螃征，將窗口內(nèi)元素直接求和是做兩次加減操作，向上文這樣一減一加也是做兩次加減操作透敌。但如果k取一個(gè)較大的值盯滚，則求和要做k-1次加減，但一減一加依舊是兩次加減酗电，計(jì)算成本被大大降低魄藕。

然后我們探討一下，窗口從最左端一直滑動(dòng)到最右端的過(guò)程中撵术，能使窗口內(nèi)元素之和最大的窗口位置背率。用idx表示窗口的位置，則代碼如下嫩与。

int sum = 0;
int max_sum = 0;
int max_idx;
for (int idx = 0; idx < nums.size(); idx++) {
    sum += nums[idx];
    if (idx >= k - 1) {
        if (sum > max_sum) {
            max_sum = sum;
            max_idx = idx - k + 1;
        }
        sum -= nums[idx - k + 1];
    }
}

2. 如何滑動(dòng)窗口找到max_sum123

分解這個(gè)問(wèn)題寝姿，我們先固定窗口3的位置，則sum3的值就是固定的了蕴纳。如果我們想得到max_sum123会油，就要在序列3前面的空間內(nèi)，找到sum1 + sum2的最大值古毛，我們用max_sum12表示翻翩。因此，則有max_sum123 = max_sum12 + sum3稻薇。

當(dāng)然idx3不可能是固定的嫂冻，讓窗口3向后滑動(dòng)一格，則窗口1和窗口2的可移動(dòng)范圍也變大了塞椎，但如果依舊想讓max_sum123得到最大值桨仿，依舊是要找到窗口1和窗口2在活動(dòng)范圍內(nèi)能得到的最大的max_sum12，并與當(dāng)前的sum3相加案狠。將計(jì)算結(jié)果與滑動(dòng)前的max_sum123比較服傍，如果更大則替換掉原先的max_sum123。

現(xiàn)在我們的問(wèn)題被分解成了max_sum12骂铁。和之前一樣吹零，我們先固定窗口2的位置，則sum2的值就固定了拉庵，那么只有當(dāng)窗口1的sum1在它的活動(dòng)范圍內(nèi)取到最大值（記為max_sum1）時(shí)灿椅，兩個(gè)窗口的元素和才能取到最大，即max_sum12 = max_sum1 + sum2。

窗口2向后滑動(dòng)了也是同樣的道理茫蛹，這里就不再贅述了操刀。

上面說(shuō)了這么多，其實(shí)重點(diǎn)只是推導(dǎo)出下面這兩個(gè)公式：

3. 代碼實(shí)現(xiàn)

最重要的兩個(gè)問(wèn)題解決了婴洼，下面繼續(xù)分析題目骨坑。

首先確定三個(gè)窗口的初始狀態(tài)。三個(gè)窗口都完全進(jìn)入數(shù)組后的第一個(gè)狀態(tài)是都位于最左端窃蹋。計(jì)算三個(gè)窗口內(nèi)的sum1卡啰、sum2静稻、sum3警没，并于max_sum1、max_sum2振湾、max_sum3進(jìn)行比較杀迹。

第三個(gè)窗口向右滑動(dòng)一格，則第二個(gè)窗口的活動(dòng)范圍就增大一格押搪。讓第二個(gè)窗口也向右滑動(dòng)一格树酪，則第一個(gè)窗口的活動(dòng)范圍也增大一格。第一個(gè)窗口向右滑動(dòng)大州，計(jì)算此時(shí)的sum1续语，與max_sum1進(jìn)行比較并更新max_sum1的值，并記錄窗口的位置max_idx1厦画。

根據(jù)前面推導(dǎo)出的關(guān)系式疮茄，繼續(xù)計(jì)算max_sum12。比較max_sum1 + sum2與max_sum2的大小根暑，如果max_sum1 + sum2大于max_sum2則替換max_sum2的值力试，并記錄此時(shí)兩個(gè)窗口的位置max_idx12_1和max_idx12_2。如果不大于排嫌，max_idx12_1和max_idx12_2的值均不改變畸裳。

注意，讓前兩個(gè)窗口內(nèi)的元素之和最大的兩窗口的位置淳地，應(yīng)該是max_idx_12和max_idx12_2——第一個(gè)窗口的位置是max_idx12_1而不能用max_idx1怖糊，這是因?yàn)樵诓粷M足max_sum1 + sum2大于max_sum2的情況下，有可能max_idx1記錄的是已經(jīng)向后滑動(dòng)的位置颇象，而max_idx12_2沒(méi)有向后滑動(dòng)伍伤，此時(shí)第一個(gè)窗口和第二個(gè)窗口就會(huì)有一個(gè)元素重合。因此我們多設(shè)立一個(gè)max_idx12_1夯到，它能保留住上一次循環(huán)時(shí)第一個(gè)窗口的位置嚷缭。在不滿足max_sum1 + sum2大于max_sum2的情況下，max_idx12_1和max_idx12_2都保留上一次循環(huán)的值即可。

max_sum123的計(jì)算和位置記錄同理阅爽，不再贅述路幸。

三個(gè)窗口每次循環(huán)都向右滑動(dòng)一格，知道第三個(gè)窗口達(dá)到數(shù)組最右端付翁，循環(huán)結(jié)束简肴。

代碼如下。

//動(dòng)態(tài)規(guī)劃
class Solution {
public:
    vector<int> maxSumOfThreeSubarrays(vector<int>& nums, int k) 
    {   
        int sum1 = 0, sum2 = 0, sum3 = 0;
        int max_sum1 = 0, max_sum12 = 0, max_sum123 = 0;

        int max_idx1 = 0, max_idx12_1 = 0, max_idx12_2 = 0;
        int max_idx123_1 = 0, max_idx123_2 = 0, max_idx123_3 = 0;

        for (int idx = k * 2; idx < nums.size(); idx++) {
            sum1 += nums[idx - 2 * k];
            sum2 += nums[idx - k];
            sum3 += nums[idx];

            if (idx >= 3 * k - 1) {
                if (sum1 > max_sum1) {
                    max_sum1 = sum1;
                    max_idx1 = idx - 3 * k + 1;
                }
                
                if (max_sum1 + sum2 > max_sum12) {
                    max_sum12 = max_sum1 + sum2;
                    max_idx12_1 = max_idx1;
                    max_idx12_2 = idx - 2 * k + 1;
                }
                
                if (max_sum12 + sum3 > max_sum123) {
                    max_sum123 = max_sum12 + sum3;
                    max_idx123_1 = max_idx12_1;
                    max_idx123_2 = max_idx12_2;
                    max_idx123_3 = idx - k + 1;
                }
                
                sum1 -= nums[idx - 3 * k + 1];
                sum2 -= nums[idx - 2 * k + 1];
                sum3 -= nums[idx - k + 1];
            }
        }
        
        return {max_idx123_1, max_idx123_2, max_idx123_3};
    }
};

滑動(dòng)窗口方法的時(shí)間復(fù)雜度為O(n)百侧，比動(dòng)態(tài)規(guī)劃算法要快許多砰识。