滑动窗口

• 209. Minimum Size Subarray Sum
  • 思路
  • C++
  • Java
  • Python
  • Go
• 3364. Minimum Positive Sum Subarray 
  • 思路
  • C++解法
    • Approach 1: Brute Force
    • Approach 2: Sliding Window (Optimized)
    • Approach 3: Prefix Sum with Sliding Window
    • Approach 4: Optimized Sliding Window with Fixed Size
• 643. Maximum Average Subarray I
  • 思路
  • C++解法
  • Java解法
  • Python解法
  • Go解法

209. Minimum Size Subarray Sum

Given an array of positive integers nums and a positive integer target, return the minimal length of a subarray whose sum is greater than or equal to target. If there is no such subarray, return 0 instead.

Example 1:

Input: target = 7, nums = [2,3,1,2,4,3]
Output: 2
Explanation: The subarray [4,3] has the minimal length under the problem constraint.

Example 2:

Input: target = 4, nums = [1,4,4]
Output: 1

Example 3:

Input: target = 11, nums = [1,1,1,1,1,1,1,1]
Output: 0

Constraints:

• 1 <= target <= 10^9
• 1 <= nums.length <= 10^5
• 1 <= nums[i] <= 10^4

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)).

思路

1. 双重for循环暴力解决
2. 单层for循环，滑动窗口

下面代码使用滑动窗口。

• Time complexity: O(n)
• Space complexity: O(1)

C++

滑动窗口解法：

class Solution {
public:
    int minSubArrayLen(int target, vector<int>& nums) {
        int minLen = numeric_limits<int>::max();
        int left = 0;
        int curSum = 0;

        for (int right = 0; right < nums.size(); right++) {
            curSum += nums[right];

            while (curSum >= target) {
                if (right - left + 1 < minLen) {
                    minLen = right - left + 1;
                }
                curSum -= nums[left];
                left++;
            }
        }

        return minLen != numeric_limits<int>::max() ? minLen : 0;        
    }
};

暴力解法：

class Solution {
public:
    int minSubArrayLen(int s, vector<int>& nums) {
        int result = INT32_MAX; // 最终的结果
        int sum = 0; // 子序列的数值之和
        int subLength = 0; // 子序列的长度
        for (int i = 0; i < nums.size(); i++) { // 设置子序列起点为i
            sum = 0;
            for (int j = i; j < nums.size(); j++) { // 设置子序列终止位置为j
                sum += nums[j];
                if (sum >= s) { // 一旦发现子序列和超过了s，更新result
                    subLength = j - i + 1; // 取子序列的长度
                    result = result < subLength ? result : subLength;
                    break; // 因为我们是找符合条件最短的子序列，所以一旦符合条件就break
                }
            }
        }
        // 如果result没有被赋值的话，就返回0，说明没有符合条件的子序列
        return result == INT32_MAX ? 0 : result;
    }
};

• 时间复杂度：O(n^2)
• 空间复杂度：O(1)

后面力扣官方更新了数据，暴力解法已经超时了。

Java

class Solution {
    public int minSubArrayLen(int target, int[] nums) {
        int minLen = Integer.MAX_VALUE;
        int left = 0;
        int curSum = 0;

        for (int right = 0; right < nums.length; right++) {
            curSum += nums[right];

            while (curSum >= target) {
                if (right - left + 1 < minLen) {
                    minLen = right - left + 1;
                }
                curSum -= nums[left];
                left++;
            }
        }
        
        return minLen != Integer.MAX_VALUE ? minLen : 0;        
    }
}

Python

class Solution:
    def minSubArrayLen(self, target: int, nums: List[int]) -> int:
        min_len = float("inf")
        left = 0
        cur_sum = 0

        for right in range(len(nums)):
            cur_sum += nums[right]

            while cur_sum >= target:
                if right - left + 1 < min_len:
                    min_len = right - left + 1
                cur_sum -= nums[left]
                left += 1
        
        return min_len if min_len != float("inf") else 0

Go

func minSubArrayLen(target int, nums []int) int {
    i := 0
    l := len(nums)  // 数组长度
    sum := 0        // 子数组之和
    result := l + 1 // 初始化返回长度为l+1，目的是为了判断“不存在符合条件的子数组，返回0”的情况
    for j := 0; j < l; j++ {
        sum += nums[j]
        for sum >= target {
            subLength := j - i + 1
            if subLength < result {
                result = subLength
            }
            sum -= nums[i]
            i++
        }
    }
    if result == l+1 {
        return 0
    } else {
        return result
    }
}

注意：题目要求子数组的和要大于或等于target

3364. Minimum Positive Sum Subarray 

You are given an integer array nums and two integers l and r. Your task is to find the minimum sum of a subarray whose size is between l and r (inclusive) and whose sum is greater than 0.

Return the minimum sum of such a subarray. If no such subarray exists, return -1.

A subarray is a contiguous non-empty sequence of elements within an array.

Example 1:

Input: nums = [3, -2, 1, 4], l = 2, r = 3

Output: 1

Explanation:

The subarrays of length between l = 2 and r = 3 where the sum is greater than 0 are:

• [3, -2] with a sum of 1
• [1, 4] with a sum of 5
• [3, -2, 1] with a sum of 2
• [-2, 1, 4] with a sum of 3

Out of these, the subarray [3, -2] has a sum of 1, which is the smallest positive sum. Hence, the answer is 1.

Example 2:

Input: nums = [-2, 2, -3, 1], l = 2, r = 3

Output: -1

Explanation:

There is no subarray of length between l and r that has a sum greater than 0. So, the answer is -1.

Example 3:

Input: nums = [1, 2, 3, 4], l = 2, r = 4

Output: 3

Explanation:

The subarray [1, 2] has a length of 2 and the minimum sum greater than 0. So, the answer is 3.

Constraints:

• 1 <= nums.length <= 100
• 1 <= l <= r <= nums.length
• -1000 <= nums[i] <= 1000

思路

方法一：暴力求解，二重循环

方法二：可变长度的滑动窗口

C++解法

Approach 1: Brute Force

Steps:

1. Iterate through all possible subarrays of size ( k ) where ( l <= k <= r ).
2. Compute the sum of each subarray.
3. Check if the sum is greater than ( 0 ), and keep track of the minimum valid sum.
4. Return the minimum valid sum or (-1) if no such subarray exists.

Complexity:

• Time Complexity: (O(n^2)) (since we calculate the sum for all subarrays).
• Space Complexity: (O(1)) (no extra space used).

Code:

class Solution {
public:
    int minSumSubarray(vector<int>& nums, int l, int r) {
        int n = nums.size();
        int minSum = INT_MAX;
        bool found = false;

        for (int start = 0; start < n; ++start) {
            int sum = 0;
            for (int end = start; end < n; ++end) {
                sum += nums[end];
                int length = end - start + 1;
                if (length >= l && length <= r && sum > 0) {
                    minSum = min(minSum, sum);
                    found = true;
                }
            }
        }

        return found ? minSum : -1;
    }
};

Approach 2: Sliding Window (Optimized)

Steps:

1. Use a sliding window of size ( l ) to ( r ).
2. Maintain the sum of elements in the current window.
3. Check if the sum is greater than ( 0 ), and update the minimum sum if valid.
4. Slide the window one element at a time, updating the sum in ( O(1) ).

Complexity:

• Time Complexity: (O(n X (r - l + 1))) (for sliding windows of varying sizes).
• Space Complexity: (O(1)).

Code:

class Solution {
public:
    int minSumSubarray(vector<int>& nums, int l, int r) {
        int n = nums.size();
        int minSum = INT_MAX;
        bool found = false;

        for (int k = l; k <= r; ++k) {
            int sum = 0;
            for (int i = 0; i < n; ++i) {
                sum += nums[i];
                if (i >= k - 1) {
                    if (sum > 0) {
                        minSum = min(minSum, sum);
                        found = true;
                    }
                    sum -= nums[i - k + 1];
                }
            }
        }

        return found ? minSum : -1;
    }
};

Approach 3: Prefix Sum with Sliding Window

Steps

1. Precompute Prefix Sum

• Create a prefix sum array where each element at index (i) stores the sum of all elements from index (0) to (i - 1).
  • Formula: prefix[i] = prefix[i - 1] + nums[i - 1].

2. Iterate Over All Valid Subarray Sizes

• For each (k) in the range ([l, r]):
  • Use the prefix sum array to calculate subarray sums in (O(1)).
  • Compare each subarray sum with the current minimum.

3. Check Validity

• If the subarray sum is greater than (0), update the minimum sum.

4. Return the Result

• If a valid subarray is found, return the minimum sum. Otherwise, return (-1).

Complexity:

• Time Complexity: (O(n X (r - l + 1))) (for sliding windows of varying sizes).
• Space Complexity: (O(1)).

Code

class Solution {
public:
    int minSumSubarray(vector<int>& nums, int l, int r) {
        int n = nums.size();
        vector<int> prefix(n + 1, 0);

        // Step 1: Compute prefix sums
        for (int i = 0; i < n; ++i) {
            prefix[i + 1] = prefix[i] + nums[i];
        }

        int minSum = INT_MAX;
        bool found = false;

        // Step 2: Iterate over all window sizes
        for (int k = l; k <= r; ++k) {
            // Sliding window over prefix sum
            for (int i = 0; i + k <= n; ++i) {
                int sum = prefix[i + k] - prefix[i]; // Subarray sum from i to i+k-1
                if (sum > 0) {
                    minSum = min(minSum, sum);
                    found = true;
                }
            }
        }

        // Step 3: Return result
        return found ? minSum : -1;
    }
};

Approach 4: Optimized Sliding Window with Fixed Size

The sliding window method allows us to efficiently calculate the sum of a subarray by updating the sum incrementally as we "slide" the window across the array. For every subarray of size (k), we:

1. Add the element at the current end of the window.
2. Remove the element at the start of the window if the window size exceeds (k).

Steps

1. Iterate over all window sizes ((k))

• Start by trying subarrays of size (l) (minimum valid size) and incrementally check sizes up to (r) (maximum valid size).
• For each (k), initialize the sliding window and calculate the sum dynamically as the window slides.

2. Use a sliding window of size (k)

• Start with the first (k) elements to initialize the sum.
• Slide the window one element at a time:
  • Add the new element at the window's end.
  • Remove the old element at the window's start.
• This ensures (O(1)) updates to the sum for each new position.

3. Check validity

• After updating the sum, check if it is greater than (0).
• If valid, compare it with the current minimum sum and update if smaller.

4. Return the result

• After evaluating all possible subarray sizes, return the smallest valid sum. If no valid subarray is found, return (-1).

Complexity:

• Time Complexity: (O(n X (r - l + 1))) (for sliding windows of varying sizes).
• Space Complexity: (O(1)).

class Solution {
public:
    int minSumSubarray(vector<int>& nums, int l, int r) {
        int n = nums.size();
        int minSum = INT_MAX;  // Stores the minimum valid sum
        bool found = false;   // Indicates if a valid subarray is found

        // Iterate over all window sizes from l to r
        for (int k = l; k <= r; ++k) {
            int sum = 0;

            // Initialize the sum for the first window of size k
            for (int i = 0; i < k; ++i) {
                sum += nums[i];
            }

            // Check the first window
            if (sum > 0) {
                minSum = min(minSum, sum);
                found = true;
            }

            // Slide the window across the array
            for (int i = k; i < n; ++i) {
                sum += nums[i];           // Add the new element at the end of the window
                sum -= nums[i - k];       // Remove the old element at the start of the window

                // Check the current window
                if (sum > 0) {
                    minSum = min(minSum, sum);
                    found = true;
                }
            }
        }

        // Return the result or -1 if no valid subarray was found
        return found ? minSum : -1;
    }
};

643. Maximum Average Subarray I

You are given an integer array nums consisting of n elements, and an integer k.

Find a contiguous subarray whose length is equal to k that has the maximum average value and return this value. Any answer with a calculation error less than 10^-5 will be accepted.

Example 1:

**Input:** nums = [1,12,-5,-6,50,3], k = 4
**Output:** 12.75000
**Explanation:** Maximum average is (12 - 5 - 6 + 50) / 4 = 51 / 4 = 12.75

Example 2:

**Input:** nums = [5], k = 1
**Output:** 5.00000

Constraints:

• n == nums.length
• 1 <= k <= n <= 10^5
• -10^4 <= nums[i] <= 10^4

思路

使用滑动窗口求特定长度的最大子列和

C++解法

class Solution {
public:
    double findMaxAverage(vector<int>& nums, int k) {
        int left = 0;
        double result = -10000000.0;
        double sum = 0;
        for(int right = 0; right < nums.size(); right++){
            sum += nums[right];
            if(right - left + 1 == k){
                double temp = sum / k;
                result = result > temp ? result : temp;
                sum -= nums[left];
                left++;
            }
        }
        return result;
    }
};

Java解法

Python解法

Go解法