长度最小的子数组
题目形容:给定一个含有 n 个正整数的数组和一个正整数 target 。
找出该数组中满足其和 ≥ target 的长度最小的 间断子数组 [nums ~l~, nums~l+1~, ..., nums~r-1~, nums~r~] ,并返回其长度。如果不存在符合条件的子数组,返回 0 。
示例阐明请见LeetCode官网。
起源:力扣(LeetCode)
链接:https://leetcode-cn.com/probl...
著作权归领扣网络所有。商业转载请分割官网受权,非商业转载请注明出处。
解法一:滑动窗口
首先,判断非凡状况,如果数组为空,间接返回0。
否则,应用滑动窗口法来判断是否存在最小的间断子数组,具体解决逻辑如下:
- 首先,申明滑动窗口的左右边界,并用minLen记录最小的间断子数组的长度;
- 遍历数组,直到右边界遍历到原数组的最初一个数字地位;
- 计算以后范畴的间断子数组的和,判断以后的和是否比target小,如果不小于,则将窗口的左边界右移,并且判断以后的间断长度是否是最小的;如果小于,则将窗口的右边界右移。
最初,判断minLen是否已找到,如果不存在则返回0;否则,返回minLen。
public class LeetCode_209 { /** * 滑动窗口 * * @param target 目标值 * @param nums 原数组 * @return */ public static int minSubArrayLen(int target, int[] nums) { // 如果数组为空,间接返回0 if (nums == null || nums.length == 0) { return 0; } // 记录最小的间断子数组的长度 int minLen = Integer.MAX_VALUE; // 滑动窗口的左右边界 int left = 0, right = 0; // 遍历直到右边界遍历到原数组的最初一个数字地位 while (right < nums.length) { int sum = 0; // 计算以后范畴的间断子数组的和 for (int i = left; i <= right; i++) { sum += nums[i]; } // 判断以后的和是否比target小,如果不小于,则将窗口的左边界右移,并且判断以后的间断长度是否是最小的;如果小于,则将窗口的右边界右移 if (sum >= target) { minLen = Math.min(minLen, right - left + 1); left++; } else { right++; } } if (minLen == Integer.MAX_VALUE) { return 0; } return minLen; } public static void main(String[] args) { // 测试用例一,冀望输入: 2 System.out.println(minSubArrayLen(7, new int[]{2, 3, 1, 2, 4, 3})); // 测试用例二,冀望输入: 0 System.out.println(minSubArrayLen(11, new int[]{1, 1, 1, 1, 1, 1, 1, 1})); }}
【每日寄语】 人生像攀登一座山,而找山寻路,却是一种学习的过程,该当在这过程中,学习笃定、沉着,学习如何从慌乱中找到活力。