leetcode-滑动窗口题目

2022/05/08 leetcode

使用滑动窗口思路:数值连续

1 剑指 Offer II 008. 和大于等于 target 的最短子数组

func minSubArrayLen(target int, nums []int) int {
	l, r := 0, 0
	maxLen := math.MaxInt
	curSum := 0
	for r < len(nums) { // 暂停条件:r到达最右侧
		curSum += nums[r]
		for curSum >= target { // 达到预期,缩减左侧窗口
			maxLen = int(math.Min(float64(r-l+1), float64(maxLen)))
			curSum -= nums[l]
			l++
		}
		r++
	}
	if maxLen == math.MaxInt {
		return 0
	}
	return maxLen
}

时间复杂度:O(n),其中 nn 是数组的长度。指针start 和 end 最多各移动 n 次。 空间复杂度:O(1)。


Search

    公众号:豆仔gogo

    豆仔gogo

    Post Directory