題目地址

https://leetcode-cn.com/problems/minimum-size-subarray-sum/

題目描述

給定一個含有 n 個正整數(shù)的數(shù)組和一個正整數(shù) target 。
找出該數(shù)組中滿足其和 ≥ target 的長度最小的 連續(xù)子數(shù)組 [numsl, numsl+1, ..., numsr-1, numsr] ，并返回其長度。如果不存在符合條件的子數(shù)組，返回 0 。

示例 1：
輸入：target = 7, nums = [2,3,1,2,4,3]
輸出：2
解釋：子數(shù)組 [4,3] 是該條件下的長度最小的子數(shù)組。
示例 2：
輸入：target = 4, nums = [1,4,4]
輸出：1
示例 3：
輸入：target = 11, nums = [1,1,1,1,1,1,1,1]
輸出：0
 
提示：
1 <= target <= 109
1 <= nums.length <= 105
1 <= nums[i] <= 105
 
進階：
如果你已經(jīng)實現(xiàn) O(n) 時間復雜度的解法, 請嘗試設計一個 O(n log(n)) 時間復雜度的解法。

思路

1. 暴力法，列舉出每個子數(shù)組，求長度最小的子數(shù)組
2. 窗口法，從0開始向右擴大窗口，直至大于等于目標值，向左縮小窗口，至不滿足大于等于目標值，然后繼續(xù)向右擴大窗口。動態(tài)計算窗口最小值。

題解

/**
 * @Author: vividzcs
 * @Date: 2021/2/19 6:45 下午
 */
public class MinSubArrayLen {
    public static void main(String[] args) {
        int target = 7;
        int[] nums = {2,3,1,2,4,3};
        int result = minSubArrayLen(target, nums);
        System.out.println(result);

        result = minSubArrayLenV2(target, nums);
        System.out.println(result);
    }

    /**
     * 執(zhí)行用時：2 ms, 在所有 Java 提交中擊敗了82.34%的用戶
     * 內(nèi)存消耗：38.2 MB, 在所有 Java 提交中擊敗了90.85%的用戶
     */
    private static int minSubArrayLenV2(int target, int[] nums) {
        if (nums.length < 0) {
            return 0;
        }
        int left = 0;
        int right = 0;
        int result = Integer.MAX_VALUE;
        int sum = nums[right];
        while (left < nums.length && right < nums.length) {
            if (sum >= target) {
                System.out.println(left + " " + right);
                result = Math.min(result, right - left + 1);
                sum -= nums[left];
                left++;
            } else {
                right++;
                if (right < nums.length) {
                    sum += nums[right];
                }
            }
        }

        if (result == Integer.MAX_VALUE || result < 0) {
            return 0;
        }
        return result;
    }

    /**
     * 執(zhí)行用時：145 ms, 在所有 Java 提交中擊敗了13.26%的用戶
     * 內(nèi)存消耗：38.6 MB, 在所有 Java 提交中擊敗了17.26%的用戶
     */
    private static int minSubArrayLen(int target, int[] nums) {
        int result = Integer.MAX_VALUE;
        for (int i=0; i<nums.length; i++) {
            int sum = nums[i];
            if (sum >= target) {
                result = Math.min(result, 1);
            }
            for (int j=i+1; j<nums.length; j++) {
                sum += nums[j];
                if (sum >= target) {
                    result = Math.min(result, j - i + 1);
                    break;
                }
            }
        }
        if (result == Integer.MAX_VALUE) {
            return 0;
        }
        return result;
    }
}