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

🔴   🔖  数组 动态规划  🔗 力扣 LeetCode

题目

Given an integer array nums and an integer k, find three non-overlapping subarrays of length k with maximum sum and return them.

Return the result as a list of indices representing the starting position of each interval (0-indexed). If there are multiple answers, return the lexicographically smallest one.

Example 1:

Input: nums = [1,2,1,2,6,7,5,1], k = 2

Output: [0,3,5]

Explanation: Subarrays [1, 2], [2, 6], [7, 5] correspond to the starting indices [0, 3, 5].

We could have also taken [2, 1], but an answer of [1, 3, 5] would be lexicographically larger.

Example 2:

Input: nums = [1,2,1,2,1,2,1,2,1], k = 2

Output: [0,2,4]

Constraints:

• 1 <= nums.length <= 2 * 10^4
• 1 <= nums[i] < 216
• 1 <= k <= floor(nums.length / 3)

题目大意

给你一个整数数组 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^4
• 1 <= nums[i] < 216
• 1 <= k <= floor(nums.length / 3)

解题思路

1. 滑动窗口

• 使用滑动窗口来计算长度为 k 的子数组的和。
• 通过减去窗口左端元素、加上窗口右端元素，可以在 O(1) 的时间内更新当前窗口的和。

2. 动态规划思路

• 维护三个变量分别存储：
  • 最佳的一个子数组和及起始索引（best_one_all 和 one_start）。
  • 最佳的两个子数组和及起始索引（best_two_all 和 two_start）。
  • 最佳的三个子数组和及起始索引（best_three_all 和 three_start）。
• 按顺序计算三个子数组的起始索引，确保没有重叠：
  • 第一个子数组起始索引范围是 [0, nums.length - 3*k]。
  • 第二个子数组起始索引范围是 [k, nums.length - 2*k]。
  • 第三个子数组起始索引范围是 [2*k, nums.length - k]。

3. 更新逻辑

• 滑动窗口每次移动时更新：
  • 当前第一个子数组的和及起始索引（如果更优）。
  • 当前前两个子数组的和及起始索引（如果更优）。
  • 当前三个子数组的和及起始索引（如果更优）。

4. 返回结果

• 最后返回记录的最佳三个子数组的起始索引。

复杂度分析

• 时间复杂度：O(n)，对于长度为 n 的数组，滑动窗口移动次数为 O(n - 3k)。
• 空间复杂度：O(1)，仅使用常数额外空间存储子数组和及索引。

代码

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number[]}
 */
var maxSumOfThreeSubarrays = function (nums, k) {
	let one_start = 0;
	let two_start = [0, k];
	let three_start = [0, k, 2 * k];

	let cur_one_sum = nums.slice(0, k).reduce((a, b) => a + b, 0);
	let cur_two_sum = nums.slice(k, 2 * k).reduce((a, b) => a + b, 0);
	let cur_three_sum = nums.slice(2 * k, 3 * k).reduce((a, b) => a + b, 0);

	let best_one_all = cur_one_sum;
	let best_two_all = cur_one_sum + cur_two_sum;
	let best_three_all = cur_one_sum + cur_two_sum + cur_three_sum;

	let one_start_i = 1;
	let two_start_i = k + 1;
	let three_start_i = k * 2 + 1;

	while (three_start_i <= nums.length - k) {
		cur_one_sum =
			cur_one_sum - nums[one_start_i - 1] + nums[one_start_i + k - 1];
		cur_two_sum =
			cur_two_sum - nums[two_start_i - 1] + nums[two_start_i + k - 1];
		cur_three_sum =
			cur_three_sum - nums[three_start_i - 1] + nums[three_start_i + k - 1];

		if (cur_one_sum > best_one_all) {
			best_one_all = cur_one_sum;
			one_start = one_start_i;
		}
		if (cur_two_sum + best_one_all > best_two_all) {
			best_two_all = cur_two_sum + best_one_all;
			two_start[0] = one_start;
			two_start[1] = two_start_i;
		}
		if (cur_three_sum + best_two_all > best_three_all) {
			best_three_all = cur_three_sum + best_two_all;
			three_start[0] = two_start[0];
			three_start[1] = two_start[1];
			three_start[2] = three_start_i;
		}
		one_start_i++;
		two_start_i++;
		three_start_i++;
	}
	return three_start;
};

相关题目

题号	标题	题解	标签	难度	力扣
123	买卖股票的最佳时机 III	[✓]	数组 动态规划	🔴	🀄️ 🔗