营销型 展示类网站模板,靖宇东兴自助建站,安徽省住房和建设厅门户网站,公司做网站都需要什么文章目录 Tag题目来源题目解读解题思路方法一#xff1a;滑动窗口 写在最后 Tag
【滑动窗口】【数组】【2023-11-19】 题目来源
689. 三个无重叠子数组的最大和 题目解读 解题思路
方法一#xff1a;滑动窗口
单个子数组的最大和
我们先来考虑一个长度为 k 的子数组的最… 文章目录 Tag题目来源题目解读解题思路方法一滑动窗口 写在最后 Tag
【滑动窗口】【数组】【2023-11-19】 题目来源
689. 三个无重叠子数组的最大和 题目解读 解题思路
方法一滑动窗口
单个子数组的最大和
我们先来考虑一个长度为 k 的子数组的最大值与取得最大值时的初始位置。可以使用固定长度的滑动窗口来解决本题。
滑动窗口是数组和字符串等问题中常用的一个概念。利用滑动窗口可以去掉重复的运算从而降低时间复杂度。滑动窗口的 “滑动” 指的是窗口每次向右移动一个位置那么该窗口内的就会增加原窗口右侧的元素并且会减少原窗口左端点的元素。
我们从数组 [0, k-1] 区间开始不断地向右滑动窗口直至窗口右端点到达数组末尾时停止。统计这一过程中长度为 k 的窗口内元素和 sum1 的最大值记为 maxSum1及其对应位置。
实现代码为
class Solution {
public:vectorint maxSumOfOneSubarray(vectorint nums, int k) {vectorint ans;int sum1 0, maxSum1 0;for (int i 0; i nums.size(); i) {sum1 nums[i];if (i k - 1) {if (sum1 maxSum1) {maxSum1 sum1;ans {maxSum1, i - k 1};}sum1 - nums[i - k 1];}}return ans;}
};两个子数组的最大和
我们可以仿照 单个子数组的最大和 问题的解题方法使用两个固定长度的滑动窗口来求解 两个子数组的最大和。
设 sum1 为第一个滑动窗口的元素和该滑动窗口从 [0, k - 1] 开始sum2 为第二个滑动窗口的元素和该滑动窗口从 [k, 2*k - 1] 开始。我们同时向右滑动这两个窗口并维护 sum1 的最大值 maxSum1 及其对应位置。每次滑动时记录当前的 maxSum1 与 sum2 之和。统计这一过程中的 maxSum1 sum2 的最大值记作 maxSum12及其对应位置。
实现代码为
class Solution {
public:vectorint maxSumOfTwoSubarrays(vectorint nums, int k) {vectorint ans;int sum1 0, maxSum1 0, maxSum1Idx 0;int sum2 0, maxSum12 0;for (int i k; i nums.size(); i) {sum1 nums[i - k];sum2 nums[i];if (i k * 2 - 1) {if (sum1 maxSum1) {maxSum1 sum1;maxSum1Idx i - k * 2 1;}if (maxSum1 sum2 maxSum12) {maxSum12 maxSum1 sum2;ans {maxSum1Idx, i - k 1};}sum1 - nums[i - k * 2 1];sum2 - nums[i - k 1];}}return ans;}
};三个子数组的最大和
在本题中可以使用三个长度为 k 的滑动窗口。设 sum1 为第一个滑动窗口的元素和该滑动窗口从 [0, k - 1] 开始sum2 为第二个滑动窗口的元素和该滑动窗口从 [k, 2*k - 1] 开始sum3 为第三个滑动窗口的元素和该滑动窗口从 [2*k, 3*k - 1] 开始。
我们同时向右滑动这三个窗口并维护 maxSum12 及其对应位置。每次滑动时记录当前的 maxSum12 与 sum3 之和。统计这一过程中的 maxSum12 sum3 的最大值记作 maxTotal及其对应位置。
对于题目要求的最小字典序由于我们是从左向右遍历的并且仅当元素和超过最大元素和时才修改最大元素和从而保证求出来的下标列表是字典序最小的。
复杂度分析
class Solution {
public:vectorint maxSumOfThreeSubarrays(vectorint nums, int k) {vectorint res;int sum1 0, maxSum1 0, maxSum1Idx 0;int sum2 0, maxSum12 0, maxSum12Idx1 0, maxSum12Idx2 0;int sum3 0, maxTotal 0;for (int i 2 * k; i nums.size(); i) {sum1 nums[i - 2 * k];sum2 nums[i - k];sum3 nums[i];if (i 3 * k - 1) {if (sum1 maxSum1) {maxSum1 sum1;maxSum1Idx i - 3 * k 1; }if (maxSum1 sum2 maxSum12) {maxSum12 maxSum1 sum2;maxSum12Idx1 maxSum1Idx;maxSum12Idx2 i - 2 * k 1;}if (maxSum12 sum3 maxTotal) {maxTotal maxSum12 sum3;res {maxSum12Idx1, maxSum12Idx2, i - k 1};}sum1 - nums[i - 3 * k 1];sum2 - nums[i - 2 * k 1];sum3 - nums[i - k 1];}}return res;}
};复杂度分析
时间复杂度 O ( n ) O(n) O(n)。
空间复杂度 O ( 1 ) O(1) O(1)。 写在最后
如果文章内容有任何错误或者您对文章有任何疑问欢迎私信博主或者在评论区指出 。
如果大家有更优的时间、空间复杂度方法欢迎评论区交流。
最后感谢您的阅读如果感到有所收获的话可以给博主点一个 哦。
