leetcode【数组—中等】209.长度最小的子数组

简介: leetcode【数组—中等】209.长度最小的子数组

题目


题目来源leetcode


leetcode地址:209. 长度最小的子数组,难度:中等。


题目描述(摘自leetcode):


给定一个含有 n 个正整数的数组和一个正整数 target 。
找出该数组中满足其和 ≥ target 的长度最小的 连续子数组 [numsl, numsl+1, ..., numsr-1, numsr] ,并返回其长度。如果不存在符合条件的子数组,返回 0 。
示例 1:
输入:target = 7, nums = [2,3,1,2,4,3]
输出:2
解释:子数组 [4,3] 是该条件下的长度最小的子数组。
示例 2:
输入:target = 4, nums = [1,4,4]
输出:1
示例 3:
输入:target = 11, nums = [1,1,1,1,1,1,1,1]
输出:0


本地调试代码:


class Solution {
    public int minSubArrayLen(int target, int[] nums) {
        ...
    }
    public static void main(String[] args) {
        int[] nums = new int[]{2,3,1,2,4,3};
        System.out.println(new Solution().minSubArrayLen(7, nums));
    }
}



题解


NO1、暴力法(O(n2))


一开始没啥思路,直接就通过使用暴力方法来进行求解。


思路:遍历一遍数组的过程中,每到一个索引位置就去求长度最小的子数组,每次求到最小子数组时就与原本临时保存的最小数(连续数)进行比较取值。


代码:时间复杂度:O(n2),实际为n+(n-1)+(n-2)…,不好求到具体的时间复杂度


public int minSubArrayLen(int target, int[] nums) {
    if (nums.length == 0 || nums == null) {
        return 0;
    }
    int minSize = nums.length + 1;
    for (int i = 0; i < nums.length; i++) {
        int num = 0;
        //从当前索引位置开始往后取到最小值,并得到符合情况的最小长度
        for (int j = i; j < nums.length; j++) {
            num+=nums[j];
            if(num>=target){
                minSize = Math.min((j - i + 1), minSize); //(j-i+1)<minSize?(j-i+1):minSize => Math.min((j - i + 1), minSize)
                break;
            }
        }
    }
    return minSize == nums.length + 1 ? 0 : minSize;//判断一下是否与初始值一致,一致的话说明没有找到符合的最小子数组
}



No2:滑动窗口(O(n))


思路:详细可见代码随想录—209.长度最小的子数组


需要有两个指针来进行配合,核心是以指针区间中的数值和进行移动。能将No1题解中的大量不必要的情况筛减掉,提升效率。
左指针用一个变量0来作为初始值;右指针使用遍历数组的索引i
  首先进行遍历,不断移动右指针到一个满足条件的位置(>=target),接着开始缩减范围以>=target为条件开始移动左指针,一旦<target就说明缩减的范围已经足够接着需要再去移动右指针往后取寻找其他更小的情况,通过左右指针进行移动筛选比之前暴力法效果好太多!


代码:时间复杂度O(n)。


每次执行for循环中的while实际上并不会执行很多次,一般也就1-3次和原本的for循环次数加起来为O(2n),可以直接看做是O(n)。
public int minSubArrayLen(int target, int[] nums) {
    if (nums.length == 0 || nums == null) {
        return 0;
    }
    int minSubLen = nums.length+1;//最大数量
    int leftCur = 0; //左指针
    int sum = 0;//用于记录当前指针区间中的值
    for (int i = 0; i < nums.length; i++) {  //i就相当于右指针
        sum += nums[i];
        while(sum>=target){   //用来移动左指针,减小区间范围,目的是为了之后其他满足sum>=target的情况
            int subLen = i - leftCur + 1;  //计算当前区间数量
            minSubLen = Math.min(subLen, minSubLen);//与之前区间进行比较,得到最小区间数量
            sum -= nums[leftCur++];//区间减小值
        }
    }
    return minSubLen == nums.length + 1 ? 0 : minSubLen;
}


相关文章
|
13天前
|
C++ Python
二刷力扣--数组
二刷力扣--数组
|
14天前
|
索引
【LeetCode刷题】二分查找:山脉数组的峰顶索引、寻找峰值
【LeetCode刷题】二分查找:山脉数组的峰顶索引、寻找峰值
|
14天前
|
算法
【经典LeetCode算法题目专栏分类】【第10期】排序问题、股票问题与TOP K问题:翻转对、买卖股票最佳时机、数组中第K个最大/最小元素
【经典LeetCode算法题目专栏分类】【第10期】排序问题、股票问题与TOP K问题:翻转对、买卖股票最佳时机、数组中第K个最大/最小元素
|
14天前
【LeetCode刷题】前缀和解决问题:742.寻找数组的中心下标、238.除自身以外数组的乘积
【LeetCode刷题】前缀和解决问题:742.寻找数组的中心下标、238.除自身以外数组的乘积
|
14天前
【LeetCode刷题】二分查找:寻找旋转排序数组中的最小值、点名
【LeetCode刷题】二分查找:寻找旋转排序数组中的最小值、点名
|
14天前
【LeetCode刷题】滑动窗口思想解决问题:长度最小的子数组、无重复字符的最长子串
【LeetCode刷题】滑动窗口思想解决问题:长度最小的子数组、无重复字符的最长子串
|
14天前
|
算法
【经典LeetCode算法题目专栏分类】【第6期】二分查找系列:x的平方根、有效完全平方数、搜索二位矩阵、寻找旋转排序数组最小值
【经典LeetCode算法题目专栏分类】【第6期】二分查找系列:x的平方根、有效完全平方数、搜索二位矩阵、寻找旋转排序数组最小值
|
13天前
|
算法 C++
【数据结构与算法】:关于时间复杂度与空间复杂度的计算(C/C++篇)——含Leetcode刷题-2
【数据结构与算法】:关于时间复杂度与空间复杂度的计算(C/C++篇)——含Leetcode刷题
|
13天前
|
算法 C++
【数据结构与算法】:关于时间复杂度与空间复杂度的计算(C/C++篇)——含Leetcode刷题-1
【数据结构与算法】:关于时间复杂度与空间复杂度的计算(C/C++篇)——含Leetcode刷题
|
14天前
|
算法
【LeetCode刷题】滑动窗口解决问题:串联所有单词的子串(困难)、最小覆盖子串(困难)
【LeetCode刷题】滑动窗口解决问题:串联所有单词的子串(困难)、最小覆盖子串(困难)