算法题/滑动窗口：给定和的最小子数组

题目

给定一个由正数组成的数组和给定正数' S '，求其总和大于或等于' S '的最小连续子数组的长度。如果不存在这样的子数组则返回0。

示例1：

输入：[2, 1, 5, 2, 3, 2], S=7
输出：2
解释：[5, 2]

示例2：

输入：[2, 1, 5, 2, 8], S=7
输出：1
解释：[8]

解答1：滑动窗口

Java

class MinSizeSubArraySum {
  public static int findMinSubArray(int S, int[] arr) {
    int windowSum = 0, minLength = Integer.MAX_VALUE;
    int windowStart = 0;
    for (int windowEnd = 0; windowEnd < arr.length; windowEnd++) {
      windowSum += arr[windowEnd]; //添加后一个元素
      //收缩窗口，直到windowSum<S
      while (windowSum >= S) {
        minLength = Math.min(minLength, windowEnd - windowStart + 1);
        windowSum -= arr[windowStart]; //减去从滑动窗口移除的元素
        windowStart++; //向前滑动窗口
      }
    }

    return minLength == Integer.MAX_VALUE ? 0 : minLength;
  }

  public static void main(String[] args) {
    int result = MinSizeSubArraySum.findMinSubArray(7, new int[] { 2, 1, 5, 2, 3, 2 });
    System.out.println("Smallest subarray length: " + result);
    result = MinSizeSubArraySum.findMinSubArray(7, new int[] { 2, 1, 5, 2, 8 });
    System.out.println("Smallest subarray length: " + result);
    result = MinSizeSubArraySum.findMinSubArray(8, new int[] { 3, 4, 1, 1, 6 });
    System.out.println("Smallest subarray length: " + result);
  }
}

JavaScript

class MinSizeSubArraySum {
  static findMinSubArray(S, arr) {
    let windowSum = 0;
    let minLength = Infinity;
    let windowStart = 0;

    for (let windowEnd = 0; windowEnd < arr.length; windowEnd++) {
      windowSum += arr[windowEnd]; // 添加后一个元素

      // 收缩窗口，直到windowSum < S
      while (windowSum >= S) {
        minLength = Math.min(minLength, windowEnd - windowStart + 1);
        windowSum -= arr[windowStart]; // 减去从滑动窗口移除的元素
        windowStart++; // 向前滑动窗口
      }
    }

    return minLength === Infinity ? 0 : minLength;
  }
}

let result = MinSizeSubArraySum.findMinSubArray(7, [2, 1, 5, 2, 3, 2]);
console.log("Smallest subarray length: " + result);
result = MinSizeSubArraySum.findMinSubArray(7, [2, 1, 5, 2, 8]);
console.log("Smallest subarray length: " + result);
result = MinSizeSubArraySum.findMinSubArray(8, [3, 4, 1, 1, 6]);
console.log("Smallest subarray length: " + result);

Python

class MinSizeSubArraySum:
    @staticmethod
    def findMinSubArray(S, arr):
        windowSum = 0
        minLength = float('inf')
        windowStart = 0

        for windowEnd in range(len(arr)):
            windowSum += arr[windowEnd]  # 添加后一个元素

            # 收缩窗口，直到windowSum < S
            while windowSum >= S:
                minLength = min(minLength, windowEnd - windowStart + 1)
                windowSum -= arr[windowStart]  # 减去从滑动窗口移除的元素
                windowStart += 1  # 向前滑动窗口

        return 0 if minLength == float('inf') else minLength


result = MinSizeSubArraySum.findMinSubArray(7, [2, 1, 5, 2, 3, 2])
print("Smallest subarray length:", result)
result = MinSizeSubArraySum.findMinSubArray(7, [2, 1, 5, 2, 8])
print("Smallest subarray length:", result)
result = MinSizeSubArraySum.findMinSubArray(8, [3, 4, 1, 1, 6])
print("Smallest subarray length:", result)

Go

package main

import (
	"fmt"
)

type MinSizeSubArraySum struct{}

func (m *MinSizeSubArraySum) findMinSubArray(S int, arr []int) int {
	windowSum := 0
	minLength := int(^uint(0) >> 1) // Equivalent to Integer.MAX_VALUE in Java
	windowStart := 0

	for windowEnd := 0; windowEnd < len(arr); windowEnd++ {
		windowSum += arr[windowEnd] // 添加后一个元素

		// 收缩窗口，直到windowSum < S
		for windowSum >= S {
			minLength = min(minLength, windowEnd-windowStart+1)
			windowSum -= arr[windowStart] // 减去从滑动窗口移除的元素
			windowStart++                  // 向前滑动窗口
		}
	}

	if minLength == int(^uint(0)>>1) {
		return 0
	}
	return minLength
}

func min(a, b int) int {
	if a < b {
		return a
	}
	return b
}

func main() {
	minSizeSubArraySum := MinSizeSubArraySum{}

	result := minSizeSubArraySum.findMinSubArray(7, []int{2, 1, 5, 2, 3, 2})
	fmt.Println("Smallest subarray length:", result)
	result = minSizeSubArraySum.findMinSubArray(7, []int{2, 1, 5, 2, 8})
	fmt.Println("Smallest subarray length:", result)
	result = minSizeSubArraySum.findMinSubArray(8, []int{3, 4, 1, 1, 6})
	fmt.Println("Smallest subarray length:", result)
}