第6期 ARTS 打卡计划

闻人的技术博客

发布于 2020-07-01 16:05:33

3960

发布于 2020-07-01 16:05:33

文章被收录于专栏：程序员闻人

ARTS 起源

关于 ARTS：一个需要持续地坚持的高效学习项目，每周写一个ARTS：Algorithm 是一道算法题，Review 是读一篇英文文章，Technique/Tips 是分享一个小技术，Share 是分享一个观点。

本周 ARTS

A：长度最小的子数组
R：Instagram Engineering’s 3 rules to a scalable cloud application architecture
T：排查 Linux 网络问题的常用工具
S：从 0 开始学大数据之 Hadoop 大数据原理与架构

Algorithm：长度最小的子数组

来源：LeetCode 209. 长度最小的子数组

难度中等359收藏分享切换为英文关注反馈给定一个含有 n 个正整数的数组和一个正整数 s ，找出该数组中满足其和 ≥ s 的长度最小的连续子数组，并返回其长度。如果不存在符合条件的连续子数组，返回 0。示例：输入：s = 7, nums = [2,3,1,2,4,3] 输出：2 解释：子数组 [4,3] 是该条件下的长度最小的连续子数组。来源：力扣（LeetCode）著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

思路：双指针法 & 滑动窗口

用一个双指针构成的滑动窗口来计算该子数组，滑动窗口的左边界为 start=0，有边界为 end=0 为起点，先遍历 end，如果发现子数组大于等于 s，那么 start+=1，继续遍历 end，用一个变量 min 记录窗口的大小，当 nums[start,end+1] 的和大于等于 s，的时候，记录 end-start+1 子数组长度。

public class Solution {

    public int minSubArrayLen(int s, int[] nums) {
        int min = Integer.MAX_VALUE;
        if (nums.length == 0) {
            return 0;
        }
        int start = 0, end = 0;
        int sum = 0;
        while (end < nums.length) {
            sum += nums[end++];
            while (sum >= s) {
                min = Math.min(min, end - start);
                sum -= nums[start++];
            }
        }
        return min == Integer.MAX_VALUE ? 0 : min;
    }

}