在计算机领域,算法是一个永恒的主题。任何计算机使用者都希望计算机能运行得更快一些或是能解决更大规模的问题。从现在开始,跟随我每天刷一道算法题吧!


在此之前,我们刷的几乎都是有关数组操作的算法题。在接下来的几天里,我们将学习 “双指针技巧”,它可以帮助我们解决许多与数组相关的问题。

双指针专题 第四天。

LeetCode #209 长度最小的子数组

题目

给定一个含有 n 个正整数的数组和一个正整数 s ,找出该数组中满足其和 ≥ s 的长度最小的连续子数组如果不存在符合条件的连续子数组,返回 0。

示例1:

输入: s = 7, nums = [2,3,1,2,4,3]
输出: 2
解释: 子数组 [4,3] 是该条件下的长度最小的连续子数组。

解题思路

滑动窗口思路:

这一道题我们会用到双指针的一种应用——滑动窗口算法。

当输出或比较的结果在原数据结构中是连续排列的时候,可以使用滑动窗口算法求解。
将两个指针比作一个窗口,通过移动指针的位置改变窗口的大小,观察窗口中的元素是否符合题意。

  1. 初始窗口中只有数组开头一个元素。
  2. 当窗口中的元素小于目标值,右指针向右移,扩大窗口。
  3. 当窗口中的元素大于目标值,比较当前窗口大小是否为最小值,左指针向右移,缩小窗口。

滑动窗口代码:

class Solution {
public int minSubArrayLen(int s, int[] nums) {
int length = nums.length;
if (length == 0)
return 0;

int left = 0; // 左指针
int right = 0; // 右指针
int sum = 0; // 窗口中元素的和
int minSize = Integer.MAX_VALUE; // 最小窗口

while(right < length){
// 窗口中的元素小于目标值,右指针向右移,扩大窗口
sum += nums[right++];

// 窗口中的元素大于目标值,左指针向右移,缩小窗口
while(sum >= s){
minSize = Math.min(minSize, right - left);
sum -= nums[left++];
}
}

return minSize == Integer.MAX_VALUE? 0:minSize;
}
}

评论