Hard

题目描述

给定一个整数数组 nums 和一个整数 k，找出三个长度为 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^4
  • 1 <= nums[i] < 2^16
  • 1 <= k <= floor(nums.length / 3)

解题思路

解题思路

这是一道经典的动态规划问题，需要找到三个不重叠的长度为 k 的子数组，使其和最大。

核心思路：

  1. 滑动窗口预处理：首先计算所有长度为 k 的子数组的和
  2. 分段动态规划：将问题分为三段来考虑
    • 左段：记录从左开始到当前位置的最大子数组位置
    • 右段：记录从当前位置到右端的最大子数组位置
    • 中段：枚举中间子数组的位置，结合左右段信息

具体步骤：

  1. 计算每个长度为 k 的子数组的和
  2. 构建 left 数组：left[i] 表示在区间 [0, i] 内最大子数组的起始位置
  3. 构建 right 数组：right[i] 表示在区间 [i, n-k] 内最大子数组的起始位置
  4. 枚举中间子数组的起始位置 mid，计算 left[mid-k] + sums[mid] + right[mid+k] 的最大值

为了保证字典序最小，在和相等时选择索引较小的位置。这种方法时间复杂度为 O(n)，空间复杂度为 O(n)。

代码实现

class Solution {
public:
    vector<int> maxSumOfThreeSubarrays(vector<int>& nums, int k) {
        int n = nums.size();
        vector<int> sums(n - k + 1);
        
        // 计算所有长度为k的子数组的和
        int sum = 0;
        for (int i = 0; i < k; i++) {
            sum += nums[i];
        }
        sums[0] = sum;
        for (int i = 1; i < n - k + 1; i++) {
            sum = sum - nums[i - 1] + nums[i + k - 1];
            sums[i] = sum;
        }
        
        // left[i]表示在[0, i]范围内最大子数组的起始位置
        vector<int> left(n - k + 1);
        int maxIdx = 0;
        for (int i = 0; i < n - k + 1; i++) {
            if (sums[i] > sums[maxIdx]) {
                maxIdx = i;
            }
            left[i] = maxIdx;
        }
        
        // right[i]表示在[i, n-k]范围内最大子数组的起始位置
        vector<int> right(n - k + 1);
        maxIdx = n - k;
        for (int i = n - k; i >= 0; i--) {
            if (sums[i] >= sums[maxIdx]) {
                maxIdx = i;
            }
            right[i] = maxIdx;
        }
        
        // 枚举中间子数组的位置
        vector<int> result(3);
        int maxSum = 0;
        for (int mid = k; mid <= n - 2 * k; mid++) {
            int l = left[mid - k];
            int r = right[mid + k];
            int totalSum = sums[l] + sums[mid] + sums[r];
            if (totalSum > maxSum) {
                maxSum = totalSum;
                result[0] = l;
                result[1] = mid;
                result[2] = r;
            }
        }
        
        return result;
    }
};

class Solution:
    def maxSumOfThreeSubarrays(self, nums: List[int], k: int) -> List[int]:
        n = len(nums)
        
        # 计算所有长度为k的子数组的和
        sums = []
        window_sum = sum(nums[:k])
        sums.append(window_sum)
        for i in range(1, n - k + 1):
            window_sum = window_sum - nums[i - 1] + nums[i + k - 1]
            sums.append(window_sum)
        
        # left[i]表示在[0, i]范围内最大子数组的起始位置
        left = [0] * (n - k + 1)
        max_idx = 0
        for i in range(n - k + 1):
            if sums[i] > sums[max_idx]:
                max_idx = i
            left[i] = max_idx
        
        # right[i]表示在[i, n-k]范围内最大子数组的起始位置
        right = [0] * (n - k + 1)
        max_idx = n - k
        for i in range(n - k, -1, -1):
            if sums[i] >= sums[max_idx]:
                max_idx = i
            right[i] = max_idx
        
        # 枚举中间子数组的位置
        max_sum = 0
        result = [0, 0, 0]
        for mid in range(k, n - 2 * k + 1):
            l = left[mid - k]
            r = right[mid + k]
            total_sum = sums[l] + sums[mid] + sums[r]
            if total_sum > max_sum:
                max_sum = total_sum
                result = [l, mid, r]
        
        return result

public class Solution {
    public int[] MaxSumOfThreeSubarrays(int[] nums, int k) {
        int n = nums.Length;
        int[] sums = new int[n - k + 1];
        
        // 计算所有长度为k的子数组的和
        int sum = 0;
        for (int i = 0; i < k; i++) {
            sum += nums[i];
        }
        sums[0] = sum;
        for (int i = 1; i < n - k + 1; i++) {
            sum = sum - nums[i - 1] + nums[i + k - 1];
            sums[i] = sum;
        }
        
        // left[i]表示在[0, i]范围内最大子数组的起始位置
        int[] left = new int[n - k + 1];
        int maxIdx = 0;
        for (int i = 0; i < n - k + 1; i++) {
            if (sums[i] > sums[maxIdx]) {
                maxIdx = i;
            }
            left[i] = maxIdx;
        }
        
        // right[i]表示在[i, n-k]范围内最大子数组的起始位置
        int[] right = new int[n - k + 1];
        maxIdx = n - k;
        for (int i = n - k; i >= 0; i--) {
            if (sums[i] >= sums[maxIdx]) {
                maxIdx = i;
            }
            right[i] = maxIdx;
        }
        
        // 枚举中间子数组的位置
        int[] result = new int[3];
        int maxSum = 0;
        for (int mid = k; mid <= n - 2 * k; mid++) {
            int l = left[mid - k];
            int r = right[mid + k];
            int totalSum = sums[l] + sums[mid] + sums[r];
            if (totalSum > maxSum) {
                maxSum = totalSum;
                result[0] = l;
                result[1] = mid;
                result[2] = r;
            }
        }
        
        return result;
    }
}

var maxSumOfThreeSubarrays = function(nums, k) {
    const n = nums.length;
    const sums = [];
    
    // 计算所有长度为k的子数组的和
    let sum = 0;
    for (let i = 0; i < k; i++) {
        sum += nums[i];
    }
    sums.push(sum);
    for (let i = 1; i < n - k + 1; i++) {
        sum = sum - nums[i - 1] + nums[i + k - 1];
        sums.push(sum);
    }
    
    // left[i]表示在[0, i]范围内最大子数组的起始位置
    const left = new Array(n - k + 1);
    let maxIdx = 0;
    for (let i = 0; i < n - k + 1; i++) {
        if (sums[i] > sums[maxIdx]) {
            maxIdx = i;
        }
        left[i] = maxIdx;
    }
    
    // right[i]表示在[i, n-k]范围内最大子数组的起始位置
    const right = new Array(n - k + 1);
    maxIdx = n - k;
    for (let i = n - k; i >= 0; i--) {
        if (sums[i] >= sums[maxIdx]) {
            maxIdx = i;
        }
        right[i] = maxIdx;
    }
    
    // 枚举中间子数组的位置
    const result = [0, 0, 0];
    let maxSum = 0;
    for (let mid = k; mid <= n - 2 * k; mid++) {
        const l = left[mid - k];
        const r = right[mid + k];
        const totalSum = sums[l] + sums[mid] + sums[r];
        if (totalSum > maxSum) {
            maxSum = totalSum;
            result[0] = l;
            result[1] = mid;
            result[2] = r;
        }
    }
    
    return result;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型值说明
时间复杂度O(n)需要遍历数组计算子数组和，构建left和right数组，以及枚举中间位置
空间复杂度O(n)需要额外的数组存储子数组和、left数组和right数组

相关题目