题目

image.png

思路

  • 思路一：由于要求时间复杂度为O(n)，所以必须是一次遍历完成，由于求的是局部最大值，因此要求每次我们要逐个比较局部的值，因此想到用双指针的滑动窗口解决，确保窗口里面i到j的和要大于s，不满足时要扩大j，如果满足的话就同时缩小i和扩大j，再判断是否满足，最后取其中的最小值

  • 思路二：由于要求时间复杂度为O(nlogn)，很容易想到要二分法，但是二分法要建立在有序的基础上，我们就要想办法构造这个有序集合，很容易发现前缀和就能满足有序，并且又能求和。

    代码

    1.   //1.双指针
    2.   public int minSubArrayLen(int s, int[] nums) {
    3.       int i = 0, sum = 0, len = Integer.MAX_VALUE;
    4.       for (int j = 0; j < nums.length; j++) {
    5.           sum += nums[j];
    6.           while (sum >= s) {
    7.               len =  Math.min(len , j - i + 1);
    8.               sum -= nums[i++];
    9.           }
    10.       }
    11.       return len == Integer.MAX_VALUE ? 0 : len;
    12.   }
    14.   //2.前缀和+二分法

    长度最小的子数组