1、刷题慢慢积累起来以后，遇到相似的题目时，会出现算法思路混淆了
2、这两道题都是对连续子数组加和进行考察，细节区别在于数组元素在209. 长度最小的子数组为正整数（窗口增加元素递增，减少元素递减），在560. 和为K的子数组为整数
3、209. 长度最小的子数组采用滑动窗口的算法，560. 和为K的子数组采用前缀和+哈希表的算法
209. 长度最小的子数组
1、有点像leetcode分类刷题：基于数组的双指针（一、基于元素移除的O(1)类型）中的快慢指针，快指针遍历数组元素，慢指针在满足一定条件时更新。
2、同时，要注意 基本子数组类型 更新窗口左边界时用while循环文章来源：https://www.toymoban.com/news/detail-686930.html
from typing import List
'''
209. 长度最小的子数组
题目描述：给定一个含有n个正整数的数组和一个正整数target。
找出该数组中满足其和 ≥target的 长度最小的 连续子数组[numsl, numsl+1, ..., numsr-1, numsr] ，并返回其长度。
如果不存在符合条件的子数组，返回 0 。
示例 1:
输入：target = 7, nums = [2,3,1,2,4,3]
输出：2
解释：子数组 [4,3] 是该条件下的长度最小的子数组
题眼：≥target的 长度最小的 连续子数组；
注意：因为这道题保证了数组中每个元素都为正，所以窗口增加元素递增，减少元素递减
思路：滑动窗口（双指针的特殊形式），设置窗口左右边界[left, right]，初始值均为0，右边界遍历数组，满足条件后，while循环更新左边界，
关键在于思考清楚窗口的左右边界如何更新（和基于数组的双指针的题目同理）
总结：这个题的思路怎么想到双指针呢？首先数组必然要遍历，需要一个指针，另外要去寻找满足条件的子数组，必然再需要另一个（和基于数组的双指针的题目同理）
'''
class Solution:
def minSubArrayLen(self, target: int, nums: List[int]) -> int:
left, right = 0, 0
s = 0
result = len(nums) + 1 # 取一个大于数组长度的值
for right in range(len(nums)):
# 1、当移动right扩大窗口，进行哪些操作
s += nums[right]
# 2、什么条件下，窗口应该暂停扩大，开始移动left缩小窗口
while s >= target:
# 3、缩小窗口进行哪些操作
# 4、更新结果
result = min(result, right - left + 1) # 滑窗[left, right]是左闭右闭区间，子数组长度==元素个数
s -= nums[left]
left += 1
right += 1
if result != len(nums) + 1: # 不存在符合条件的子数组：所有元素加起来都小于target
return result
return 0
if __name__ == "__main__":
obj = Solution()
while True:
try:
in_line = input().strip().split('=')
target = int(in_line[1].split(',')[0].strip())
nums = [int(n) for n in in_line[2].split(']')[0].split('[')[1].split(',')]
print(obj.minSubArrayLen(target, nums))
except EOFError:
break
560. 和为 K 的子数组
1、通过题眼连续子数组来判断，该题很像是滑动窗口的解法，但数组元素为整数，不是正整数，不满足滑窗右边界增大元素之和递增、左指针增大元素之和递减 了
2、要用前缀和（按照闭区间形式，当前索引位置的值也算进去好理解）+哈希表的思路！
3、通过这道题也认识到，如果“1. 两数之和”不是限定了样例只存在一个答案，其哈希表更新的逻辑有缺陷文章来源地址https://www.toymoban.com/news/detail-686930.html
from typing import List
'''
560. 和为 K 的子数组
题目描述：给你一个整数数组 nums 和一个整数 k ，请你统计并返回 该数组中和为 k 的连续子数组的个数 。
示例 1:
输入：nums = [1,1,1], k = 2
输出：2
题眼：连续子数组，很像是滑动窗口的解法，但数组元素为整数，不是正整数，不满足滑窗右边界增大元素之和递增、左指针增大元素之和递减 了
思路：无法用滑动窗口了；要用前缀和（按照闭区间形式，当前索引位置的值也算进去好理解）+哈希表的思路！
“1. 两数之和”的扩展：通过这道题也认识到，如果“1. 两数之和”不是限定了样例只存在一个答案，其哈希表更新的逻辑有缺陷
'''
class Solution:
def subarraySum(self, nums: List[int], k: int) -> int:
result = 0
hashTable = {0: 1} # 这里保证了对 包含起始元素的连续子数组 的判断
prefixSum = 0
for n in nums: # 查找 以当前遍历元素n对应的索引位置为 右边界的连续子数组
prefixSum += n # 前缀和（按照闭区间形式，当前索引位置的值也算进去好理解）
# 1、先找 以当前遍历元素n对应的索引位置 之前的前缀和是否存在满足条件的
if prefixSum - k in hashTable:
result += hashTable[prefixSum - k]
# 2、再将当前遍历元素n对应的索引位置 的前缀和添加到hashDict
if prefixSum not in hashTable:
hashTable[prefixSum] = 1
else:
hashTable[prefixSum] += 1
return result
if __name__ == "__main__":
obj = Solution()
while True:
try:
in_line = input().strip().split('=')
nums = [int(n) for n in in_line[1].split('[')[1].split(']')[0].split(',')]
k = int(in_line[2].strip())
print(obj.subarraySum(nums, k))
except EOFError:
break
到了这里，关于leetcode分类刷题：易混题辨析一、209. 长度最小的子数组 vs 560. 和为K的子数组的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
