网站长尾词挖掘,合肥网站营销,东莞网站设计知名乐云seo,镇江网站制作优化讲解题目#xff1a;长度最小的子数组
给定一个含有 n 个正整数的数组和一个正整数 target #xff0c;找出该数组中满足其和 ≥ target 的长度最小的连续子数组。如果不存在符合条件的连续子数组#xff0c;返回 0。示例: 输入: target 7, nums [2,3,1,2,4,3]
输出: 2
解…讲解题目长度最小的子数组
给定一个含有 n 个正整数的数组和一个正整数 target 找出该数组中满足其和 ≥ target 的长度最小的连续子数组。如果不存在符合条件的连续子数组返回 0。示例: 输入: target 7, nums [2,3,1,2,4,3]
输出: 2
解释: 子数组 [4,3] 是该条件下的长度最小的连续子数组。这类型题类似于规划问题有约束和 targrt有目标函数长度最小
暴力解题思路
就是首先遍历窗口从1到len(nums)然后再遍历该窗口长度下的所有数组计算和因为窗口长度从小遍历所以只要出现和 target 就结束计算时间复杂度是N2
def minSubArrayLen(target, nums):for win in range(1, len(nums) 1):# print(fwin:{win})for left in range(len(nums) - win 1):left max(0, left)right min(left win, len(nums))val nums[left:right]if sum(val) target:return winelse:passreturn 0
改进解题思路
初始化 left right 0把区间 [left, right] 称为一个「窗口」。不断地增加 right 指针扩大窗口 [left, right]直到窗口中的字符串符合要求。停止增加 right转而不断增加 left 指针缩小窗口 [left, right]直到窗口中的字符串不再符合要求。重复第 2 和第 3 步直到 right 到达字符串 S 的尽头。
def minSubArrayLen(s, nums):start 0end 0min_length len(nums) 1sum_nums 0while end len(nums):sum_nums nums[end]while sum_nums s:min_length min(min_length, end - start 1)sum_nums - nums[start]start 1end 1return 0 if min_length len(nums) 1 else min_length
习题1
给你一个字符串 S、一个字符串 T请在字符串 S 里面找出包含 T 所有字母的最小子串示例输入: S ADOBECODEBANC, T ABC
输出: BANC思路 滑动窗口我们维护一个可变的窗口这个窗口的左右边界分别用指针 start 和 end 表示。我们通过移动 end 指针来扩大窗口直到窗口包含 T 中所有的字母。然后我们尝试通过移动 start 指针来缩小窗口以得到最小的满足条件的子串。 字符频率我们需要记录 T 中字符的频率并在窗口中保持一个字典来统计窗口内的字符频率。每当窗口内的字符完全满足 T 中所有字符时我们就更新最小子串的长度。
def minSubArrayLen(S, T):if not S or not T:return t_dic Counter(T)start 0flag 0min_len float(inf)min_substr s_dic Counter()for end in range(len(S)):char S[end]s_dic[char] 1# print(fsub_str:{sub_str})# print(fs_dic:{s_dic})if char in t_dic.keys() and t_dic[char] s_dic[char]:flag 1# print(fflag:{flag})while flag len(t_dic) and start end:if end - start 1 min_len:min_len end - start 1min_substr S[start:end 1]else:pass# print(fmin_substr:{min_substr})s_dic[S[start]] - 1if S[start] in t_dic.keys() and t_dic[S[start]] s_dic[S[start]]:flag - 1start 1# print(fs_dic:{s_dic})# print(fflag:{flag})# print(fres_final:{res_final})return min_substr
习题2
给你一个整数数组 nums 和一个整数 k 。请你从 nums 中满足下述条件的全部子数组中找出最大子数组和子数组的长度是 k且
子数组中的所有元素 各不相同 。
返回满足题面要求的最大子数组和。如果不存在子数组满足这些条件返回 0 。子数组 是数组中一段连续非空的元素序列。示例 输入nums [1,5,4,2,9,9,9], k 3
输出15
解释nums 中长度为 3 的子数组是
- [1,5,4] 满足全部条件和为 10 。
- [5,4,2] 满足全部条件和为 11 。
- [4,2,9] 满足全部条件和为 15 。
- [2,9,9] 不满足全部条件因为元素 9 出现重复。
- [9,9,9] 不满足全部条件因为元素 9 出现重复。
因为 15 是满足全部条件的所有子数组中的最大子数组和所以返回 15 。
思路
用字典 nums_dic 维护窗口内元素的个数用 max_sum 维护窗口内的数之和遍历数组窗口进入进出一个元素需要维护 nums_dic 和 max_sum若满足条件lennums_dic k则更新 max_val
def maximumSubarraySum(nums, k):if len(nums) 0 or k 0:return 0if k 1:return max(nums)max_val float(-inf)nums_dic Counter(nums[:k-1])max_sum sum(nums[:k-1])for i in range(k - 1, len(nums)):nums_dic[nums[i]] 1max_sum max_sum nums[i]# print(fnums_dic:{nums_dic})# print(fmax_sum:{max_sum})if len(nums_dic) k:max_val max(max_sum, max_val)nums_dic[nums[i - k 1]] - 1if nums_dic[nums[i - k 1]] 0:del nums_dic[nums[i - k 1]]max_sum - nums[i - k 1]return 0 if max_val float(-inf) else max_val
