跳至正文

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

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

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.

给定一个整数数组nums和一个整数数组k,找到三个长度为k且总和最大的不重叠子数组并返回它们。

以索引列表的形式返回结果,这些索引表示每个间隔(索引为0)的起始位置。如果有多个答案,返回按字典顺序最小的一个。

public class Solution {
    public int[] MaxSumOfThreeSubarrays(int[] nums, int k) {
        int[] ans = new int[3];
        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.Length; ++i) {
            //注意这里的起始是从2k开始的
            //从这开始依次计算三个滑动窗口内元素的和
            sum1 += nums[i - k * 2];
            sum2 += nums[i - k];
            sum3 += nums[i];
            //要同时维护三个滑动窗口和的值
            //边滑动边比较
            //只有加完了k个元素才会进入到下面的if语句中
            if (i >= k * 3 - 1) {
                if (sum1 > maxSum1) {
                    maxSum1 = sum1;
                    maxSum1Idx = i - k * 3 + 1;
                }
                //如果窗口1的值比目前的最大值来得大
                //更新最大值以及最大值所代表的子数组下标
                if (maxSum1 + sum2 > maxSum12) {
                    maxSum12 = maxSum1 + sum2;
                    maxSum12Idx1 = maxSum1Idx;
                    maxSum12Idx2 = i - k * 2 + 1;
                }
                //窗口1的最大值和窗口2的值比窗口1+2的最大值来得大
                //更新窗口1+2的最大值,更新子数组1和子数组2的坐标
                if (maxSum12 + sum3 > maxTotal) {
                    maxTotal = maxSum12 + sum3;
                    ans[0] = maxSum12Idx1;
                    ans[1] = maxSum12Idx2;
                    ans[2] = i - k + 1;
                }
                //判断窗口1+2的最大值和窗口3的值比总的最大值来得大
                //更新最大值,同时开始给答案数组赋值
                //分别为子数组1,子数组2,当前
                sum1 -= nums[i - k * 3 + 1];
                sum2 -= nums[i - k * 2 + 1];
                sum3 -= nums[i - k + 1];
            }
        }
        return ans;
    }
}

我怀疑原题中文翻译可能中文真的学不好了

断句甚至没有我拖到有道让ai翻译来的好

经典阅读理解是吧

抛开这个来说这题对我还是cv题

我一开始的思路是单个滑动窗口加上哈希表的键值对来存储

但是写一半才发现这样没有办法判断重叠

看了题解好家伙,直接三个滑动窗口

而且三个滑动窗口都要维持好自己的值

直接把我整懵了

麻了兄弟们

希望明天能来道简单题让我重拳出击

发表评论

您的电子邮箱地址不会被公开。