建商城站用WordPress,seo技术培训茂名,广州网页制作设计营销,公关网站建设题目#xff1a;
689. 三个无重叠子数组的最大和
给你一个整数数组 nums 和一个整数 k #xff0c;找出三个长度为 k 、互不重叠、且全部数字和#xff08;3 * k 项#xff09;最大的子数组#xff0c;并返回这三个子数组。
以下标的数组形式返回结果#xff0c;数组中…题目
689. 三个无重叠子数组的最大和
给你一个整数数组 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 * 1041 nums[i] 2161 k floor(nums.length / 3)
解答 class Solution {public int[] maxSumOfOneSubarray(int[] nums, int k) {int[] ans new int[1];int sum1 0, maxSum1 0;for (int i 0; i nums.length; i) {sum1 nums[i];if (i k - 1) {if (sum1 maxSum1) {maxSum1 sum1;ans[0] i - k 1;}sum1 - nums[i - k 1];}}return ans;}
} class Solution {public int[] maxSumOfTwoSubarrays(int[] nums, int k) {int[] ans new int[2];int sum1 0, maxSum1 0, maxSum1Idx 0;int sum2 0, maxSum12 0;for (int i k; i nums.length; 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[0] maxSum1Idx;ans[1] i - k 1;}sum1 - nums[i - k * 2 1];sum2 - nums[i - k 1];}}return ans;}
}代码
class Solution {public int[] maxSumOfThreeSubarrays(int[] nums, int k) {int[] ansnew int[3];int sum10,maxSum10,maxSum1Idx0;int sum20,maxSum120,maxSum12Idx10,maxSum12Idx20;int sum30,maxTotal0;for(int i2*k;inums.length;i){sum1nums[i-2*k];sum2nums[i-k];sum3nums[i];if(i3*k-1){if(sum1maxSum1){maxSum1sum1;maxSum1Idxi-3*k1;}if(maxSum1sum2maxSum12){maxSum12maxSum1sum2;maxSum12Idx1maxSum1Idx;maxSum12Idx2i-2*k1;}if(maxSum12sum3maxTotal){maxTotalmaxSum12sum3;ans[0]maxSum12Idx1;ans[1]maxSum12Idx2;ans[2]i-k1;}sum1-nums[i-3*k1];sum2-nums[i-2*k1];sum3-nums[i-k1];}}return ans;}
}
结果
