移动商城网站开发选择,vs2008可以做网站,页面设计高度,html怎么做网页给定一个含有 n 个正整数的数组和一个正整数 s #xff0c;找出该数组中满足其和 ≥ s 的长度最小的 连续 子数组#xff0c;并返回其长度。如果不存在符合条件的子数组#xff0c;返回 0。
示例#xff1a; 输入#xff1a;s 7, nums [2,3,1,2,4,3] 输出#xff1a;…给定一个含有 n 个正整数的数组和一个正整数 s 找出该数组中满足其和 ≥ s 的长度最小的 连续 子数组并返回其长度。如果不存在符合条件的子数组返回 0。
示例 输入s 7, nums [2,3,1,2,4,3] 输出2 解释子数组 [4,3] 是该条件下的长度最小的子数组。
提示 1 target 10^9 1 nums.length 10^5 1 nums[i] 10^5
暴力解法 两个for循环然后不断的寻找符合条件的子序列时间复杂度很明显是O(n^2)。
滑动窗口解【根据当前子序列和大小的情况不断调节子序列的起始位置。从而将O(n^2)暴力解法降为O(n)】
class Solution {public int minSubArrayLen(int target, int[] nums) {int i 0;int result nums.length 1;int sum 0; for (int j 0; j nums.length - 1; j) {sum nums[j];while (sum target) {result Math.min(j - i 1, result);sum - nums[i];i;}}if (result nums.length 1) {return 0;}return result;}
}
另有解
class Solution {
// 滑动窗口public int minSubArrayLen(int s, int[] nums) {int left 0;int sum 0;int result Integer.MAX_VALUE;for (int right 0; right nums.length; right) {sum nums[right];while (sum s) {result Math.min(result, right - left 1);sum - nums[left];}}return result Integer.MAX_VALUE ? 0 : result;}
}
