云游戏网站在线玩,诺德中心做网站,做网站直接从网上的icon吗,求个网站知乎1、刷题慢慢积累起来以后#xff0c;遇到相似的题目时#xff0c;会出现算法思路混淆了 2、这两道题都是对连续子数组加和进行考察#xff0c;细节区别在于数组元素在209. 长度最小的子数组为正整数#xff08;窗口增加元素递增#xff0c;减少元素递减#xff09;#… 1、刷题慢慢积累起来以后遇到相似的题目时会出现算法思路混淆了 2、这两道题都是对连续子数组加和进行考察细节区别在于数组元素在209. 长度最小的子数组为正整数窗口增加元素递增减少元素递减在560. 和为K的子数组为整数 3、209. 长度最小的子数组采用滑动窗口的算法560. 和为K的子数组采用前缀和哈希表的算法 209. 长度最小的子数组 1、有点像leetcode分类刷题基于数组的双指针一、基于元素移除的O(1)类型中的快慢指针快指针遍历数组元素慢指针在满足一定条件时更新。 2、同时要注意 基本子数组类型 更新窗口左边界时用while循环 from typing import List209. 长度最小的子数组
题目描述给定一个含有n个正整数的数组和一个正整数target。
找出该数组中满足其和 ≥target的 长度最小的 连续子数组[numsl, numsl1, ..., 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, 0s 0result 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 1right 1if result ! len(nums) 1: # 不存在符合条件的子数组所有元素加起来都小于targetreturn resultreturn 0if __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:break560. 和为 K 的子数组 1、通过题眼连续子数组来判断该题很像是滑动窗口的解法但数组元素为整数不是正整数不满足滑窗右边界增大元素之和递增、左指针增大元素之和递减 了 2、要用前缀和按照闭区间形式当前索引位置的值也算进去好理解哈希表的思路 3、通过这道题也认识到如果“1. 两数之和”不是限定了样例只存在一个答案其哈希表更新的逻辑有缺陷 from typing import List560. 和为 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 0hashTable {0: 1} # 这里保证了对 包含起始元素的连续子数组 的判断prefixSum 0for n in nums: # 查找 以当前遍历元素n对应的索引位置为 右边界的连续子数组prefixSum n # 前缀和按照闭区间形式当前索引位置的值也算进去好理解# 1、先找 以当前遍历元素n对应的索引位置 之前的前缀和是否存在满足条件的if prefixSum - k in hashTable:result hashTable[prefixSum - k]# 2、再将当前遍历元素n对应的索引位置 的前缀和添加到hashDictif prefixSum not in hashTable:hashTable[prefixSum] 1else:hashTable[prefixSum] 1return resultif __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
