209. Minimum Size Subarray Sum Medium

1/**
2 * [209] Minimum Size Subarray Sum
3 *
4 * Given an array of positive integers nums and a positive integer target, return the minimal length of a contiguous subarray [numsl, numsl+1, ..., numsr-1, numsr] of which the sum is greater than or equal to target. If there is no such subarray, return 0 instead.
5 *  
6 * Example 1:
7 *
8 * Input: target = 7, nums = [2,3,1,2,4,3]
9 * Output: 2
10 * Explanation: The subarray [4,3] has the minimal length under the problem constraint.
11 *
12 * Example 2:
13 *
14 * Input: target = 4, nums = [1,4,4]
15 * Output: 1
16 *
17 * Example 3:
18 *
19 * Input: target = 11, nums = [1,1,1,1,1,1,1,1]
20 * Output: 0
21 *
22 *  
23 * Constraints:
24 *
25 * 1 <= target <= 10^9
26 * 1 <= nums.length <= 10^5
27 * 1 <= nums[i] <= 10^5
28 *
29 *  
30 * Follow up: If you have figured out the O(n) solution, try coding another solution of which the time complexity is O(n log(n)).
31 */
32pub struct Solution {}
33
34// problem: https://leetcode.com/problems/minimum-size-subarray-sum/
35// discuss: https://leetcode.com/problems/minimum-size-subarray-sum/discuss/?currentPage=1&orderBy=most_votes&query=
36
37// submission codes start here
38
39impl Solution {
40    pub fn min_sub_array_len(target: i32, nums: Vec<i32>) -> i32 {
41        let mut start: usize = 0;
42        let mut end: usize = 0;
43        let mut sum = 0;
44        let mut ans = i32::MAX;
45
46        while end < nums.len() {
47            while end < nums.len() && sum < target {
48                sum += nums[end];
49                end += 1;
50            }
51
52            if sum < target {
53                break;
54            }
55
56            while start < end && sum >= target {
57                sum -= nums[start];
58                start += 1;
59            }
60
61            if end - start + 1 < ans as usize {
62                ans = (end - start) as i32 + 1;
63            }
64        }
65        if ans == i32::MAX {
66            0
67        } else {
68            ans
69        }
70    }
71}
72
73// submission codes end
74
75#[cfg(test)]
76mod tests {
77    use super::*;
78
79    #[test]
80    fn test_209() {
81        assert_eq!(Solution::min_sub_array_len(7, vec![2, 3, 1, 2, 4, 3]), 2);
82    }
83}
84