本文共 1002 字,大约阅读时间需要 3 分钟。
给定一个正整数数组nums以及一个正整数s,要求从nums找出最短的连续区间,使得区间内数字的和大于等于s,返回区间中元素的个数。规定:若找不到这样的区间,则返回0.例子:
记录两个指针变量start和curIdx,start表示当前所找区间的左端点,curIdx为遍历到的数组当前位置。以及另外一个变量subSum,记录区间[start, curIdx)的和。
当有subSum + nums[idx] >= s时,我们应该再满足subSum + nums[idx] >= s的前提下,尽可能增大start(缩小区间的长度)
最后就是更新区间的最短长度啦。。
class Solution { public int minSubArrayLen(int s, int[] nums) { // curIdx为当前遍历到的位置 start为满足区间的最小左位置 subSum为nums在[start,curIdx)的和 int min = Integer.MAX_VALUE, curIdx = 0, start = 0, subSum = 0; while (curIdx < nums.length) { // 如果找到一个curIdx使得[start,curIdx)的和满足大于等于s 那么需要尽可能地增大start(缩小区间),同时满足subSum + nums[curIdx] >= s if (subSum + nums[curIdx] >= s) { while (subSum + nums[curIdx] >= s) { subSum -= nums[start++]; } min = Math.min(min, curIdx - (start - 1) + 1); } subSum += nums[curIdx++]; } return min == Integer.MAX_VALUE ? 0 : min; }}
思维思路很重要。
转载地址:http://caesi.baihongyu.com/