209. 长度最小的子数组

题目描述

给定一个含有 n 个正整数的数组和一个正整数 target 。

找出该数组中满足其和 ≥ target 的长度最小的 连续子数组 [numsl, numsl+1, ..., numsr-1, numsr] ，并返回其长度。如果不存在符合条件的子数组，返回 0 。

解题思路

哎写出来了但是很长，用双指针维护一个区间，相当于是循环不变量，

有一个观察：就是找到一个可行解后，第二个元素开始的可行解的最后一个元素一定大于或等于当前最后一个元素

所以不断地右侧生长去找到一个可行解，然后左侧缩小去尝试更小的解

#![allow(unused)]
fn main() {
struct Solution {}

impl Solution {
    pub fn min_sub_array_len(target: i32, nums: Vec<i32>) -> i32 {
        let n = nums.len();
        let mut a = 0;
        let mut b = 0;
        let mut s = 0;
        let mut res = 0;
        while s < target && b < n {
            s += nums[b];b += 1;
        }
        if s < target &&  b == n { return 0 }
        res = b;
        loop {

            while s >= target && a < b {
                s -= nums[a];
                res = res.min(b - a);
                a += 1;
            }
            while s < target && b < n {
                s += nums[b];b += 1;
            }
            if s >= target {
                res = res.min(b - a);
            }
            if b == n && s < target { break }
        }

        res as i32
    }
}
}

学习感想

首先要思考 如果用一个for循环，那么应该表示 滑动窗口的起始位置，还是终止位置。

如果只用一个for循环来表示 滑动窗口的起始位置，那么如何遍历剩下的终止位置？

此时难免再次陷入 暴力解法的怪圈。

所以 只用一个for循环，那么这个循环的索引，一定是表示 滑动窗口的终止位置。

原来是滑动窗口，只用一个变量来表示结束的位置

#![allow(unused)]
fn main() {
struct Solution {}

impl Solution {
    pub fn min_sub_array_len(target: i32, nums: Vec<i32>) -> i32 {
        let n = nums.len();
        let mut res = i32::MAX;
        let mut s = 0;
        let mut a = 0;
        for b in 0..n {
            s += nums[b];
            while s >= target {
                res = res.min((b - a + 1) as i32);
                s -= nums[a];
                a += 1;
            }
        }
        if res == i32::MAX {0} else {res as i32}
    }
}

}

在闭包中使用pattern matching来去除变量前边的引用的时候，有时候不要去除多了

    pub fn min_sub_array_len(nums: Vec<i32>) {
        nums.iter().scan(1i32, |&mut st, &x| {
            st += x;
            Some(st)
        });
    }

类似这个时候，st绑定到的就永远都是输入的那个1 到闭包函数内了，起不到修改闭包外的1的效果。

所以这个引用就不要自动匹配掉了，就手动解引用吧

思路：前缀和+双指针

#![allow(unused)]
fn main() {
struct Solution {}
impl Solution {
    pub fn min_sub_array_len(target: i32, nums: Vec<i32>) -> i32 {
        // prefix sum
        let pre_sum: Vec<i32> = nums.iter().scan(0i32, |st, &x| {
            *st += x;
            Some(*st)
        }).collect();
        let idx: usize = pre_sum.partition_point(|&x| x < target);
        if idx == nums.len() { return 0i32 }
        let mut res: usize = idx + 1usize;
        let mut right: usize = idx;
        let mut left: usize = 0usize;
        while right < nums.len() {
            while pre_sum[right] - pre_sum[left] >= target {
                left += 1usize;
            }
            let candidate: usize = right - left + 1usize;
            res = std::cmp::min(candidate, res);
            right += 1usize;
        }
        res as i32
    }
}
}

#![allow(unused)]

fn main() {
struct Solution {}

impl Solution {
    pub fn min_sub_array_len(target: i32, nums: Vec<i32>) -> i32 {
        let mut sum: i32 = 0i32;
        let mut left: usize = 0usize;
        let mut res: usize = usize::MAX;
        for right in 0usize..nums.len() {
            sum += nums[right];
            while sum >= target {
                res = std::cmp::min(res, right - left + 1usize);
                sum -= nums[left];
                left += 1usize;
            }
        }
        match res {
            usize::MAX => 0,
            _ => res as i32,
        }
    }
}
}