题目描述
给你一个整数数组 nums 和一个整数 k ，找出三个长度为 k 、互不重叠、且 3 * k 项的和最大的子数组，并返回这三个子数组。
以下标的数组形式返回结果，数组中的每一项分别指示每个子数组的起始位置（下标从 0 开始）。如果有多个结果，返回字典序最小的一个。
难度：困难
美好而轻松的12月结束了
解题代码
// 滑动窗口 func maxSumOfThreeSubarrays(nums []int, k int) (ans []int) { // sum1 是当前滑动窗口中数的和 // maxSum1 是经历过的所有窗口和最大的数 // maxSum1Idx 是拥有最大和窗口的下标 var sum1, maxSum1, maxSum1Idx int // maxSum12 是两个窗口经历过最大的数的和 // maxSum12Idx1 是使第一个窗口和第二个窗口中的数总和最大的第一个窗口的下标 // maxSum12Idx1 是使第一个窗口和第二个窗口中的数总和最大的第二个窗口的下标 var sum2, maxSum12, maxSum12Idx1, maxSum12Idx2 int // maxTotal 是三个窗口中的数总和 var sum3, maxTotal int for i := k * 2; i < len(nums); i++ { // 窗口滑动 sum1 += nums[i-k*2] sum2 += nums[i-k] sum3 += nums[i] if i >= k*3-1 { // 判断sum1是否为最大值，并记录下标 if sum1 > maxSum1 { maxSum1 = sum1 maxSum1Idx = i - k*3 + 1 } // 判断是maxSum12否为最大值，并记录下标 if maxSum1+sum2 > maxSum12 { maxSum12 = maxSum1 + sum2 maxSum12Idx1, maxSum12Idx2 = maxSum1Idx, i-k*2+1 } // 判断maxTotal是否为最大值,并录入下标 if maxSum12+sum3 > maxTotal { maxTotal = maxSum12 + sum3 ans = []int{maxSum12Idx1, maxSum12Idx2, i - k + 1} } // 将窗口边界的值去除 sum1 -= nums[i-k*3+1] sum2 -= nums[i-k*2+1] sum3 -= nums[i-k+1] } } return }
提交结果
