讲解题目:长度最小的子数组
给定一个含有 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(f'win:{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(f'sub_str:{sub_str}')# print(f's_dic:{s_dic}')if char in t_dic.keys() and t_dic[char] == s_dic[char]:flag += 1# print(f'flag:{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(f'min_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(f's_dic:{s_dic}')# print(f'flag:{flag}')# print(f'res_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),若满足条件(len(nums_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(f'nums_dic:{nums_dic}')# print(f'max_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