leetcode面试准备:Minimum Size Subarray Sum

时间:2021-12-30 03:59:02

leetcode面试准备:Minimum Size Subarray Sum

1 题目

Given an array of n positive integers and a positive integer s, find the minimal length of a subarray of which the sum ≥ s. If there isn't one, return 0 instead.

For example, given the array [2,3,1,2,4,3] and s = 7,

the subarray [4,3] has the minimal length under the problem constraint.

接口:public int minSubArrayLen(int s, int[] nums)

2 思路

题意

给定一个包含n个正整数的数组和一个正整数s,找出其满足和sum ≥ s的子数组的最小长度。如果不存在这样的子数组,返回0

例如,给定数组 [2,3,1,2,4,3]与s = 7,

子数组[4,3]具有满足题设条件的最小长度。

解题思路

O(n^2)解法:贪心法,要点:一个子数组是结果,一定有某个为起点的位置。网上说:滑动窗口法。不知道是怎么解的。

O(nlogn)解法:二分枚举,思路是,我们建立一个比原数组长一位的sums数组,其中sums[i]表示nums数组中[0, i - 1]的和,然后我们对于sums中每一个值sums[i],用二分查找法找到子数组的右边界位置,使该子数组之和大于sums[i] + s,然后我们更新最短长度的距离即可。

3 代码

    /**
* Time:O(n^2) Space:O(1) 有更好的解法,时间复杂度:O(nlogn)
*/
public int minSubArrayLen(int s, int[] nums) {
int min = Integer.MAX_VALUE;
int len = nums.length;
for (int i = 0; i < len; i++) {
int count = 0, sum = 0;
for (int j = i; j < len; j++) {
sum += nums[j];
count++;
if (sum >= s) {
min = Math.min(min, count);
break;
}
}
}
return min == Integer.MAX_VALUE ? 0 : min;
}

4 总结

二分法的解法,不是很明白。手动走一遍,二分法的代码。