LeetCode 209.長度最小的子數組

題目描述

給定一個正整數數組 nums 和一個正整數 target，找出連續子數組的最小長度，使得子數組的和大于或等于 target。如果不存在符合條件的子數組，返回 0。

Java 實現代碼

public class Solution {public int minSubArrayLen(int target, int[] nums) {int n = nums.length;int left = 0, sum = 0, minLength = Integer.MAX_VALUE;for (int right = 0; right < n; right++) {sum += nums[right]; // 擴展窗口，加入當前元素// 窗口內的和大于等于 target 時，嘗試縮小窗口while (sum >= target) {minLength = Math.min(minLength, right - left + 1);sum -= nums[left]; // 移動左指針，縮小窗口left++;}}return minLength == Integer.MAX_VALUE ? 0 : minLength;}
}

解題思路

1. 滑動窗口：使用兩個指針 left 和 right 來表示當前窗口的邊界，窗口的右邊界逐步擴展，直到窗口內的和大于等于 target。

2. 窗口收縮：每當當前窗口的和大于等于 target 時，嘗試通過移動左指針（即收縮窗口）來找到最小的符合條件的子數組。每次更新最小長度。

3. 返回結果：在遍歷完數組后，若未找到符合條件的子數組，則返回 0；否則返回最小長度。

復雜度分析

• 時間復雜度：O(n)，其中 n 是數組的長度。由于每個元素最多被訪問兩次（一次是右指針擴展，另一次是左指針收縮），因此時間復雜度是 O(n)。
• 空間復雜度：O(1)，只用了常數級別的額外空間。

舉例說明執行過程

假設輸入數組 nums = [2, 3, 1, 2, 4, 3]，target = 7。

1. 初始化：

   • left = 0, sum = 0, minLength = Integer.MAX_VALUE

2. 遍歷右指針：

   • right = 0，sum = 0 + nums[0] = 2，sum = 2，不滿足條件 sum >= 7，繼續擴展。
   • right = 1，sum = 2 + nums[1] = 5，sum = 5，不滿足條件 sum >= 7，繼續擴展。
   • right = 2，sum = 5 + nums[2] = 6，sum = 6，不滿足條件 sum >= 7，繼續擴展。
   • right = 3，sum = 6 + nums[3] = 8，sum = 8，滿足條件 sum >= 7，此時子數組為 [2, 3, 1, 2]，長度為 4，更新 minLength = 4。

3. 收縮窗口：

   • 由于滿足 sum >= target，我們嘗試通過移動 left 來縮小窗口：
   • left = 0，sum = 8，縮小窗口，sum -= nums[0] = 8 - 2 = 6，left = 1，sum = 6，不滿足 sum >= 7，繼續擴展右指針。

4. 繼續遍歷：

   • right = 4，sum = 6 + nums[4] = 10，滿足 sum >= 7，此時子數組為 [3, 1, 2, 4]，長度為 4，但 minLength 仍然保持 4。

5. 收縮窗口：

   • left = 1，sum = 10，繼續縮小窗口，sum -= nums[1] = 10 - 3 = 7，此時 sum >= target，子數組為 [1, 2, 4]，長度為 3，更新 minLength = 3。

6. 繼續遍歷：

   • right = 5，sum = 7 + nums[5] = 10，滿足 sum >= 7，此時子數組為 [1, 2, 4, 3]，長度為 4，但 minLength 保持為 3。

7. 收縮窗口：

   • left = 2，sum = 10，繼續縮小窗口，sum -= nums[2] = 10 - 1 = 9，仍然滿足 sum >= 7，子數組為 [2, 4, 3]，長度為 3，minLength 保持為 3。
   • left = 3，sum = 9，繼續縮小窗口，sum -= nums[3] = 9 - 2 = 7，滿足 sum >= 7，子數組為 [4, 3]，長度為 2，更新 minLength = 2。

8. 結束遍歷：

   • 右指針已經遍歷完整個數組，最終得到 minLength = 2。