[数据结构与算法]【LeetCode每日一题】【2021/12/8】689. 三个无重叠子数组的最大和

689. 三个无重叠子数组的最大和

LeetCode: 689. 三个无重叠子数组的最大和

$困难$

给你一个整数数组 nums 和一个整数 k ，找出三个长度为 k 、互不重叠、且 3 * k 项的和最大的子数组，并返回这三个子数组。
以下标的数组形式返回结果，数组中的每一项分别指示每个子数组的起始位置（下标从 0 开始）。如果有多个结果，返回字典序最小的一个。

示例 1：

输入：nums = [1,2,1,2,6,7,5,1], k = 2
输出：[0,3,5]
解释：子数组 [1, 2], [2, 6], [7, 5] 对应的起始下标为 [0, 3, 5]。
也可以取 [2, 1], 但是结果 [1, 3, 5] 在字典序上更大。

示例 2：

输入：nums = [1,2,1,2,1,2,1,2,1], k = 2
输出：[0,2,4]

提示：

• 1 <= nums.length <= 2 * 10⁴
• 1 <= nums[i] < 2¹⁶
• 1 <= k <= floor(nums.length / 3)

方法1：滑动窗口

因为题目要求在原数组上找出3个子数组，所以这题使用滑动窗口来解决会比较简单。

第1个窗口在最左边时（起始下标为0），第1个窗口的范围为 [0, k-1]。由于3个子数组互不重叠，所以第2个窗口必然不会从0开始，而是从下标 k 开始。同理，第3个窗口从下标 2k 开始。

我们每次将3个窗口一起往右移动一位，然后记录下每个窗口的最大值，以及对应的下标：

 1  2 [1  2][6  7][5  1]
 1 [2  1][2  6][7  5] 1
[1  2][1  2][6  7] 5  1

1. 变量 sum1，sum2，sum3 用于动态地维护每个窗口在每一步的最大值；
2. 变量 mSum1 用于存放第1个窗口的最大和，对于这个最大和，我们还需要变量 mSum1Index 来存放对应的起始位下标；
3. 变量 mSum12 用于存放 2个窗口综合考虑的最大和，也就是 第1个窗口的最大值 mSum1 和 第2个窗口当前的总和 sum2。这个时候，由于这个最大和是由窗口1最大和和当前的自身一起构成的，所以说构成这个最大和的窗口1不一定是当前的窗口1：

• [5 2][2 3] 1
  当前窗口1的和sum1为7；窗口2的和sum2为5。mSum12为mSum1=sum1=7+sum2=5，等于12。构成mSum12的窗口1下标记为mSum12Index1=0，窗口2下标记为mSum12Index2=2。
• 5 [2 2][3 1]
  当前窗口1的和sum1为4，窗口2的和sum2为4。此时4+4<mSum12=12。因此到了这一步，当前的窗口1是[2 2]，但构成mSum12的窗口1还是[5 2]。
  所以构成mSum12的窗口1和窗口2的位置需要单独记，为mSum12Index1和mSum12Index2。

4. 同理，对于mSum123来说，它是由mSum12+sum3，存放3个窗口综合考虑的最大和，构成mSum123的是2个窗口综合考虑的最大和加上当前自身的sum3。而且对于它来说，构成它的窗口1下标、窗口2下标、窗口3下标也要单独记录。
5. 由于本题有3个窗口，而mSum123就是综合考虑下的最大和，而它记录的3个下标也就是构成它的3个窗口的下标。最后这3个下标就是答案，只要返回这3个下标即可。

在下面的代码中，i为窗口3的起始点。窗口1的起始下标为0，窗口2的起始下标为k，窗口3的起始下标为k+k

#include <vector>
using namespace std;
class Solution
{
public:
    vector<int> maxSumOfThreeSubarrays(vector<int> &nums, int k)
    {
        const int n = nums.size();
        int sum1 = 0, mSum1 = 0, mSum1Index = 0;
        int sum2 = 0, mSum12 = 0, mSum12Index1 = 0, mSum12Index2 = 0;
        int sum3 = 0, mSum123 = 0, mSum123Index1 = 0, mSum123Index2 = 0, mSum123Index3 = 0;
        for (int i = (k << 1); i < n; i++)
        {
            sum1 += nums[i - (k << 1)];
            sum2 += nums[i - k];
            sum3 += nums[i];
            if (i >= 3 * k - 1)
            {
                if (sum1 > mSum1)
                {
                    mSum1 = sum1;
                    mSum1Index = i - 3 * k + 1;
                }
                if (mSum1 + sum2 > mSum12)
                {
                    mSum12 = mSum1 + sum2;
                    mSum12Index1 = mSum1Index;
                    mSum12Index2 = i - (k << 1) + 1;
                }
                if (mSum12 + sum3 > mSum123)
                {
                    mSum123 = mSum12 + sum3;
                    mSum123Index1 = mSum12Index1;
                    mSum123Index2 = mSum12Index2;
                    mSum123Index3 = i - k + 1;
                }
                sum1 -= nums[i - k * 3 + 1];
                sum2 -= nums[i - (k << 1) + 1];
                sum3 -= nums[i - k + 1];
            }
        }
        return {mSum123Index1, mSum123Index2, mSum123Index3};
    }
};

复杂度分析

• 时间复杂度：$O(n)$

• 空间复杂度：$O(1)$。我们只需要常量空间来存储若干变量。

参考结果

Accepted
43/43 cases passed (16 ms)
Your runtime beats 96.47 % of cpp submissions
Your memory usage beats 99.41 % of cpp submissions (19.5 MB)