package com.zmz.algorithm.array;

/**
 * @author 张明泽
 * Create by 2022/5/23 9:46
 * 长度最小的子数组
 * LeetCode-209
 */
public class SmallestSubarray {
    public static void main(String[] args) {
        int[] arr = {2,3,1,2,4,3};
        int target = 7;
        int result = subarrayLength2(arr,target);
        System.out.println(result);
    }

    /**
     * 暴力解法
     */
    public static int subarrayLength(int[] arr, int target) {
        int result = Integer.MAX_VALUE;
        for (int i = 0; i < arr.length; i++) {
            int num = 0;
            int index = 0;
            for (int j = i; j < arr.length; j++) {
                num = num + arr[j];
                index++;
                if (num >= target) {
                    result = Math.min(result,index);
                    break;
                }
            }
        }
        return result == Integer.MAX_VALUE ? 0 : result;
    }
    /**
     * 双指针 滑动窗口
     * O(n) while是常数阶
     */
    public static int subarrayLength2(int[] arr, int target) {
        int result = Integer.MAX_VALUE;
        int num = 0;
        int left = 0;
        for (int right = 0; right < arr.length; right++) {
            num += arr[right];
            // 不能是if 左指针右移可能还是 >= target
            while (num >= target) {
                // 有可能右移比以前的次数还大就不要赋值了
                result = Math.min(right - left + 1,result);
                num = num - arr[left];
                left++;
            }
        }
        return result == Integer.MAX_VALUE ? 0 : result;
    }
}