设计公司网站建设模板图,注册公司没有地址怎么解决,html所有标签及其属性汇总,搜索引擎有哪些分类题目 思路#xff1a;首先是长度为k的子数组的和。这个好计算。题目要求返回的是三个和最大的子数组的第一个数字的下标。下标要尽可能小。如果只要求这样#xff0c;题目就很简单了。还有个要求是各个子数组不重叠。要想不重叠首先得要求下标不重叠。子数组1下标是:0,1,2首先是长度为k的子数组的和。这个好计算。题目要求返回的是三个和最大的子数组的第一个数字的下标。下标要尽可能小。如果只要求这样题目就很简单了。还有个要求是各个子数组不重叠。要想不重叠首先得要求下标不重叠。子数组1下标是:0,1,2子数组2下标如果是1,2,3那肯定会重叠。其次要计算出每个子数组的最大值最小值。在找下个子数组的时候范围不能在这之间。我应该是傻眼了。需要考虑的因素比较多。看别人怎么解吧。 学习看了别人的解法明白题目意思了解错了。不重叠的子数组就是指下标不重叠而不是各个值不重叠。要返回的三个下标(idx1,idx2,idx3) 满足idx2idx1kidx2idx1kidx2>=idx1+k 并且 idx3idx2kidx3idx2kidx3>=idx2+k。 还要学习的一点是当计算了长度为k的子数组的和计算之后其实得到了一个sums的数组。sums[i]表示以i为起点的长度为k的子数组的和。sums的长度是n-k1。如此看待问题会比较简单一些。 对于求这三个下标我一开始的做法是 int max1 sums[0],max2 sums[0k],max3 sums[02*k];int idx1 0,idx2 k,idx3 2*k;for (i 1; i k; i) {if (sums[i] max1) {max1 sums[i];idx1 i;}if (ik n sums[ik] max2) {max2 sums[ik];idx2 ik;}if (i2*k n sums[i2*k] max3) {max3 sums[i2*k];idx3 i2*k;}}
这样做的问题是可能idx2没有变化idx1变化了。这样他们的差值就不是k就不能符合条件了。所以需要固定idx2的位置。nsums.length那么idx1∈[0,idx2−k]idx1∈[0,idx2−k]idx1 \in [0,idx2-k] 并且 idx3∈[idx21,n−1]idx3∈[idx21,n−1]idx3 \in [idx2+1,n-1]。而idx2能够取值的范围是[k,n−k−1][k,n−k−1][k,n-k-1]。(n是原始数组长度)。
当idx2位置固定对于idx1应该是[0,idx2-k]那个最大数的下标。这个问题可以用动态规划解决。用一个数组先保存从[0,当前位置]值最大的下标。动态转移方程式 如果sums[i]sums[left[i−1]]sums[i]sums[left[i−1]]sums[i]>sums[left[i-1]]则left[i]ileft[i]ileft[i] = i否则left[i]left[i−1]left[i]left[i−1]left[i] = left[i-1]。当然这里不用动态规划那就每次循环一下从0到idx2-k找到最大值的下标。
右边也是一样。当idx2位置固定对于idx3应该是[idx21,n-1]那个最大数的下标。用动态规划解决。用一个数组先保存从[当前位置,n-1]值最大的下标。动态转移方程式 如果sums[i]sums[right[i1]]sums[i]sums[right[i1]]sums[i]>=sums[right[i+1]]则right[i]iright[i]iright[i] = i否则right[i]right[i1]right[i]right[i1]right[i] = right[i+1]。这里的条件是>=是因为结果要求返回下标最小值。
学习链接
public int[] maxSumOfThreeSubarrays(int[] nums, int k) {int n nums.length;//计算和因为入参都是正数所以不需要初始化sums否则可以都初始化为Integer.MIN_VALUE;int[] sums new int[n];//这步可以优化//0,1 1,2 2,3 3,4 4,5 5,6int sum 0;for (int i 0; i n; i) {sum nums[i];if(ik) sum - nums[i-k];if(ik-1) sums[i-k1] sum; }//与左边的数组比较int[] left new int[n-k1];int best 0;for(int i0;ileft.length;i){if(sums[i]sums[best]) best i;left[i] best;}//跟右边的数组比较int[] right new int[n-k1];best right.length - 1;for(int i right.length -1;i0;i--){if(sums[i]sums[best]) best i;right[i] best;}int idx1 -1,idx2 -1,idx3 -1;for (int j k; j right.length-k; j) {int l left[j-k],r right[jk];if(idx1-1 || (sums[idx1]sums[idx2]sums[idx3] sums[l]sums[j]sums[r])){idx1 l;idx2 j;idx3 r;}}return new int[]{idx1,idx2,idx3};}
复杂度分析时间复杂度O(n)空间复杂度O(n)。
