【Leetcode 209】长度最小的子数组 —— 滑动窗口|双指针

简介: 我们可以使用双指针解决本题,定义两个指针 i 和 j 分别表示子数组(滑动窗口窗口)的开始位置和结束位置,维护变量 sum 存储子数组中的元素和。每一轮迭代中,每当 sum >= target 则记录子数组最小长度,移动慢指针。在每一轮迭代最后,移动快指针

209. 长度最小的子数组

给定一个含有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

题目分析

我们可以使用双指针解决本题,定义两个指针 i 和 j 分别表示子数组(滑动窗口窗口)的开始位置和结束位置,维护变量 sum 存储子数组中的元素和。

每一轮迭代中,每当 sum >= target 则记录子数组最小长度,移动慢指针。在每一轮迭代最后,移动快指针

双指针顾名思义,就是同时使用两个指针,在序列、链表结构上指向的是位置,在树、图结构中指向的是节点,通过或同向移动,或相向移动来维护、统计信息

经典双指针的数组遍历,更多案例可见 Leetcode 双指针详解

class Solution {
   
   
    public int minSubArrayLen(int target, int[] nums) {
   
   
        int min = Integer.MAX_VALUE, sum = 0;
        int i = 0, j = 0;
        while(j < nums.length){
   
   
            sum += nums[j];
            while(sum >= target){
   
   
                min = Math.min(min, j - i + 1);
                sum -= nums[i++];
            }
            j++;
        }
        return min == Integer.MAX_VALUE ? 0 : min;
    }
}
相关文章
|
1月前
|
算法
LeetCode刷题---21.合并两个有序链表(双指针)
LeetCode刷题---21.合并两个有序链表(双指针)
|
1月前
|
算法
LeetCode刷题---19. 删除链表的倒数第 N 个结点(双指针-快慢指针)
LeetCode刷题---19. 删除链表的倒数第 N 个结点(双指针-快慢指针)
|
9天前
|
算法 测试技术
每日一题:LeetCode-209. 长度最小的子数组(滑动窗口)
每日一题:LeetCode-209. 长度最小的子数组(滑动窗口)
|
1月前
|
存储 算法
LeetCode刷题--- 61. 旋转链表(快慢指针+闭合为环)
LeetCode刷题--- 61. 旋转链表(快慢指针+闭合为环)
|
1月前
|
算法 索引
LeetCode刷题--- 138. 复制带随机指针的链表(哈希表+迭代)
LeetCode刷题--- 138. 复制带随机指针的链表(哈希表+迭代)
|
1月前
|
存储 算法 索引
LeetCode刷题---链表经典问题(双指针)
LeetCode刷题---链表经典问题(双指针)
|
1月前
|
算法
LeetCode刷题---160. 相交链表(双指针-对撞指针)
LeetCode刷题---160. 相交链表(双指针-对撞指针)
|
1月前
|
算法 索引
LeetCode刷题---142. 环形链表 II(双指针-快慢指针)
LeetCode刷题---142. 环形链表 II(双指针-快慢指针)
|
1月前
|
算法 索引
LeetCode刷题---141. 环形链表(双指针-快慢指针)
LeetCode刷题---141. 环形链表(双指针-快慢指针)
|
19天前
|
机器学习/深度学习 算法
力扣刷题日常(一)
力扣刷题日常(一)
19 2