您的问题似乎不完整,您是想询问如何将一个子串从某个字符串中提取出来,还是有其他关于子串的问题?请提供更详细的信息,这样我才能给出准确的回答。
摘要:子串 (1) 和为 k 的子数组(前缀和) """ 给你一个整数数组 nums 和一个整数 k,请你统计并返回该数组中和为 k 的子数组的个数 输入:nums =
子串
(1) 和为 k 的子数组(前缀和)
"""
给你一个整数数组 nums 和一个整数 k,请你统计并返回该数组中和为 k 的子数组的个数
输入:nums = [1,2,3], k = 3
输出:2
"""
res = 0
presums = collections.defaultdict(int)
presums[0] = 1
presum = 0
for num in nums:
presum += num
# 每个前缀和 presum-k 代表着一个和为 k 的子数组
res += presums[presum-k]
presums[presum] += 1
return res
(2) 滑动窗口最大值(优先队列)
"""
给你一个整数数组 nums,有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧,返回滑动窗口中的最大值
输入:nums = [1,3,-1,-3,5,3,6,7], k = 3
输出:[3,3,5,5,6,7]
"""
res = []
q = collections.deque()
for i, num in enumerate(nums):
# 维护 q 的单调性
while q and nums[q[-1]] <= num:
q.pop()
q.append(i)
if i-q[0] >= k:
q.popleft()
if i >= k-1:
res.append(nums[q[0]])
return res
(3) 最小覆盖子串
"""
给定两个字符串 s 和 t,长度分别是 m 和 n,返回 s 中的最短窗口子串,使得该子串包含 t 中的每一个字符(包括重复字符)。如果没有这样的子串,返回空字符串
输入:s = "ADOBECODEBANC", t = "ABC"
输出:"BANC"
"""
need = collections.Counter(t)
missing = len(t)
left = 0
start = 0
min_len = float('inf')
for right, char in enumerate(s):
if need[char] > 0:
missing -= 1
need[char] -= 1
while missing == 0:
if right-left+1 < min_len:
start = left
min_len = right-left+1
need[s[left]] += 1
if need[s[left]] > 0:
missing += 1
left += 1
return "" if min_len == float('inf') else s[start:start+min_len]
数组
(1) 最大子数组和
"""
给你一个整数数组 nums,请你找出一个具有最大和的连续子数组(子数组最少包含一个元素),返回其最大和。
"""
res = float('-inf')
pre_sums = float('-inf')
for num in nums:
pre_sums = max(pre_sums+num, num)
res = max(res, pre_sums)
return res
(2) 合并区间
"""
以数组 intervals 表示若干个区间的集合,其中单个区间为 intervals[i] = [starti, endi]。请你合并所有重叠的区间,并返回 一个不重叠的区间数组,该数组需恰好覆盖输入中的所有区间。
