前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >leetcode每日一题:689.三个无重叠子数组的最大和

leetcode每日一题:689.三个无重叠子数组的最大和

作者头像
用户3578099
发布2021-12-11 11:18:21
3400
发布2021-12-11 11:18:21
举报
文章被收录于专栏:AI科技时讯

题目

来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/maximum-sum-of-3-non-overlapping-subarrays

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

解法

  • 使用三个大小为 k 的滑动窗口。设sum_1 为第一个滑动窗口的元素和,该滑动窗口从 [0,k-1] 开始;sum_2 为第二个滑动窗口的元素和,该滑动窗口从[k,2k−1] 开始;sum_3 为第三个滑动窗口的元素和,该滑动窗口从[2k,3k−1] 开始。

同时向右滑动这三个窗口,维护 maxSum_{12}及其对应位置。每次滑动时,计算当前 maxSum_{12}{sum}_3 之和。统计这一过程中{maxSum}_{12} +{sum}_3 的最大值及其对应位置。

对于题目要求的最小字典序,由于是从左向右遍历的,并且仅当元素和超过最大元素和时才修改最大元素和,从而保证求出来的下标列表是字典序最小的。

  • python
代码语言:javascript
复制
class Solution:
    def maxSumOfThreeSubarrays(self, nums: List[int], k: int) -> List[int]:
        ans = []
        sum1, maxSum1, maxSum1Idx = 0, 0, 0
        sum2, maxSum12, maxSum12Idx = 0, 0, ()
        sum3, maxTotal = 0, 0
        for i in range(k * 2, len(nums)):
            sum1 += nums[i - k * 2]
            sum2 += nums[i - k]
            sum3 += nums[i]
            if i >= k * 3 - 1:
                if sum1 > maxSum1:
                    maxSum1 = sum1
                    maxSum1Idx = i - k * 3 + 1
                if maxSum1 + sum2 > maxSum12:
                    maxSum12 = maxSum1 + sum2
                    maxSum12Idx = (maxSum1Idx, i - k * 2 + 1)
                if maxSum12 + sum3 > maxTotal:
                    maxTotal = maxSum12 + sum3
                    ans = [*maxSum12Idx, i - k + 1]
                sum1 -= nums[i - k * 3 + 1]
                sum2 -= nums[i - k * 2 + 1]
                sum3 -= nums[i - k + 1]
        return ans
  • c++
代码语言:javascript
复制
class Solution {
public:
    vector<int> maxSumOfThreeSubarrays(vector<int> &nums, int k) {
        vector<int> ans;
        int sum1 = 0, maxSum1 = 0, maxSum1Idx = 0;
        int sum2 = 0, maxSum12 = 0, maxSum12Idx1 = 0, maxSum12Idx2 = 0;
        int sum3 = 0, maxTotal = 0;
        for (int i = k * 2; i < nums.size(); ++i) {
            sum1 += nums[i - k * 2];
            sum2 += nums[i - k];
            sum3 += nums[i];
            if (i >= k * 3 - 1) {
                if (sum1 > maxSum1) {
                    maxSum1 = sum1;
                    maxSum1Idx = i - k * 3 + 1;
                }
                if (maxSum1 + sum2 > maxSum12) {
                    maxSum12 = maxSum1 + sum2;
                    maxSum12Idx1 = maxSum1Idx;
                    maxSum12Idx2 = i - k * 2 + 1;
                }
                if (maxSum12 + sum3 > maxTotal) {
                    maxTotal = maxSum12 + sum3;
                    ans = {maxSum12Idx1, maxSum12Idx2, i - k + 1};
                }
                sum1 -= nums[i - k * 3 + 1];
                sum2 -= nums[i - k * 2 + 1];
                sum3 -= nums[i - k + 1];
            }
        }
        return ans;
    }
};
复杂度分析
  • 时间复杂度:
    • O(N) : 其中 n 是数组nums 的长度
  • 空间复杂度
    • O(1) : 只需要常数空间来存放若干变量
参考
  • https://leetcode-cn.com/problems/maximum-sum-of-3-non-overlapping-subarrays/solution/san-ge-wu-zhong-die-zi-shu-zu-de-zui-da-4a8lb/
本文参与 腾讯云自媒体同步曝光计划,分享自微信公众号。
原始发表:2021-12-09,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 AI科技时讯 微信公众号,前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 题目
  • 解法
    • 复杂度分析
      • 参考
      领券
      问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档