文章目录
- 1. 长度最小的子数组（模板）
- 2. 无重复字符的最长字串
- 3. 最小覆盖字串
- 4. 加油站
- 5. 替换字串得到平衡字符串
1. 长度最小的子数组（模板）
- 题目分析
直接用步骤分析示例1，[]表示窗口，min_length表示满足条件的最短子数组，sum表示窗口内元素的总值：
- [2],3,1,2,4,3 min_length=100001，sum=2 < target=7
- [2,3],1,2,4,3 min_length=100001，sum=5 < target=7
- [2,3,1],2,4,3 min_length=100001，sum=6 < target=7
- [2,3,1,2],4,3 min_length=4， sum=8 >= target=7
- PS：只要sum>=target，就尝试将左窗口向右移动，若仍满足条件，就更新min_length，不行就继续
- [2,3,1,2,4],3 min_length=5， sum=12 >= target=7
- 2,[3,1,2,4],3 min_length=4， sum=10 >= target=7
- 2,3,[1,2,4],3 min_length=3， sum=7 >= target=7
- 2,3,[1,2,4,3] min_length=4， sum=10 >= target=7
- 2,3,1,[2,4,3] min_length=3， sum=9 >= target=7
- 2,3,1,2,[4,3] min_length=2， sum=7 >= target=7
- 最后返回min_length=2
- 代码实现
def minSubArrayLen(target, nums):
"""
:type target: int
:type nums: List[int]
:rtype: int
"""
n = len(nums)
# l表示左窗口的位置，r表示右窗口的位置
l = r = 0
# sum表示窗口内的元素总值
sum = nums[0]
# 如果第一个元素的值就大于等于target，直接返回
if sum >= target:
return 1
# 设置成100001是因为测试用例的数组长度最长为100000
min_length = 100001
# 循环n - 1次
for i in range(1, n):
# 右窗口肯定是要一直移动的，不存在每次循环不移动的情况
r += 1
sum += nums[r]
# 如果sum去掉靠近左窗口的那个元素后仍然大于sum，就该减小窗口的长度了
while sum - nums[l] >= target:
sum -= nums[l]
l += 1
# 经过上述步骤后，当来到右窗口此时的位置时，满足条件的窗口长度就得到了
if sum >= target:
min_length = min(min_length, r - l + 1)
# 数组所有元素的总和加起来都小于target，min_length就返回0
return 0 if min_length == 100001 else min_length
- 精简版
def minSubArrayLen(target, nums):
"""
:type target: int
:type nums: List[int]
:rtype: int
"""
n = len(nums)
l = r = 0
min_length = 100001
sum = 0
while r < n:
sum += nums[r]
while sum - nums[l] >= target:
sum -= nums[l]
l += 1
if sum >= target:
min_length = min(min_length, r - l + 1)
r += 1
return 0 if min_length == 100001 else min_length
2. 无重复字符的最长字串
注意s字符串包含：字母、数字、符号和空格
- 题目分析：
以abcabcbb为例，max_length表示最长无重复字串字串，l表示左窗口，r表示右窗口：
- [a]bcabcbb max_length=1
- [ab]cabcbb max_length=2
- [abc]abcbb max_length=3
- [abca]bcbb
- 下面这一步就很重要了，l=max(l,a上一次出现位置+1)
- a[bca]bcbb max_length=3
- a[bcab]cbb l=max(l,b上一次出现位置+1)
- ab[cab]cbb max_length=3
- ab[cabc]bb l=max(l,c上一次出现位置+1)
- abc[abc]bb max_length=3
- abc[abcb]b l=max(l,b上一次出现位置+1)
- abcab[cb]b max_length=3
- abcab[cbb] l=max(l,b上一次出现位置+1)
- abcabcb[b] max_length=3
- 代码实现
def lengthOfLongestSubstring(s):
"""
:type s: str
:rtype: int
"""
n = len(s)
# 字母、数字、空格和一些符号的ascii码都在0~255之间
pos = [-1] * 255
l = 0
max_length = 0
for r in range(n):
# 在r移动到下一个字符位置时，一定要先让l获取上次这个字符出现的位置并且加1
l = max(l, pos[ord(s[r])] + 1)
# 然后再更新这个字符出现的位置
pos[ord(s[r])] = r
# 最后通过比较获得wu'c
max_length = max(max_length, r - l + 1)
return max_length
3. 最小覆盖字串
- 题目分析
1. 拿一个cnts数组统计t串中字符的出现次数，total记录t中每个字符出现次数的总和
2. 首先，t中字符每出现一次，cnts[ord(t[i])] -= 1
3. 然后开始循环s字符串
4. 如果遇到出现次数小于0的，total就减-1
5. 每循环一次，该字符的出现次数就加1（我们只关注t中的字符，s中其它字符正常加就行了，后面不会涉及到它们）
6. 当total == 0时，也就是说当前窗口中已经包含了t中所有字符
7. 开始判断，左窗口所指向的字符出现次数是否大于0，大于0左窗口就可以向右移动了
8. PS：当total第一次等于0时，表示窗口中恰好有t中每个字符，且它们的出现次数都为0，后续可能会有多余的，它们的出现次数就会大于0，s中其它字符最开始都是0，只要在窗口中，它们的出现次数就会大于0
9. 然后判断当前窗口的长度跟最小覆盖字串的长度比较，取较小的那个
cnts是统计所有字符的出现次数，初始化为0
- 首先是将t串中每个字符的出现次数减1，也就是说，除了t串中的字符出现次数是负数，其它字符的出现次数都是0
- 然后就是只要有一个字符进窗口，出现次数加1
- 当左窗口字符出现次数大于0时，就可以考虑将其删除了
- 代码实现
def minWindow(s, t):
"""
:type s: str
:type t: str
:rtype: str
"""
n = len(s)
m = len(t)
# 如果s串长度小于m长度，s就不可能有长度大于等于m的字串
if n < m:
return ""
total = m
# 计数数组
cnts = [0] * 255
# 给t串中每种字符出现次数为负数
for i in range(m):
cnts[ord(t[i])] -= 1
l = 0
target = ''
min_length = 100001
# 开始遍历s串
for r in range(n):
# 能满足下面if语句条件的一定是t串中的字符
if cnts[ord(s[r])] < 0:
total -= 1
# 不管是哪个串中的字符，次数都要加1
cnts[ord(s[r])] += 1
# total==0表示窗口中已经包含了t串所有字符
if total == 0:
# 开始判断左窗口可不可以移动
while cnts[ord(s[l])] > 0:
cnts[ord(s[l])] -= 1
l += 1
# 取最小覆盖字串的长度
if r - l + 1 < min_length:
min_length = r - l + 1
target = s[l : r + 1]
return target
4. 加油站
- 题目分析
用左窗口遍历一遍加油站即可，此时左窗口就相当于起点，右窗口就从左窗口开始向后遍历，只要出现油不够的情况，左窗口就向右移动。
可以将gas和cost数组合并来看，例如：
gas = [1,2,3,4,5]
cost = [3,4,5,1,2]
combine = [-2,-2,-2,3,3]
combine[0]表示从第0个加油站开到第1个加油站倒欠2升油，所以无法以第0个加油站为起点，开到第一个加油站
combine[3]表示从第4个加油站开到第5个加油站多出了3升油，所以能以第4个加油站为起点，开到第五个加油站
- 代码
def canCompleteCircuit(gas, cost):
"""
:type gas: List[int]
:type cost: List[int]
:rtype: int
"""
n = len(gas)
# sum表示路上的总油量，只要油量小于0了，就不能走
sum = 0
# len表示一共走了几个加油站
length = 0
for l in range(n):
while sum >= 0:
# 如果从某个加油站出发，能走完一圈，就返回那个加油站的位置
if length == n:
return l
r = (l + length) % n
length += 1
sum += gas[r] - cost[r]
# 走到这说明sum<0了，那么左窗口就该移动了，且sum要减去左窗口移动之前所在位置的那个值，len也要减1
sum -= gas[l] - cost[l]
length -= 1
# 如果以每个加油站为起点出发，sum最后都会小于0，就返回-1
return -1
5. 替换字串得到平衡字符串
- 题目分析
思路：
1. 先统计每种字符的出现次数
2. 然后用窗口框柱一段字符，假设窗口外的每种字符出现次数不等于 n/4，判断只替换窗口内的字符能否使窗口外的每种字符字符出现次数都变成n/4
3. 如果该窗口不行，那么它的子窗口一定不行（这里没想出为什么）如果[l,r-1]不行，[l,r]行，那么[l+1,r]也有可能行，[l+1,r-1]就一定不行
4. 那么怎么实现第二步？
假如窗口长度为8，窗口外面字符出现次数为Q->18,W->19,E->16,R->19，要求是每种字符出现20次
8-(20-18) = 6
6-(20-19) = 5
5-(20-16) = 1
1-(20-19) = 0
最后剩余0，表示能行
如果外面某种字符超过了平均出现次数，那么这个窗口一定不行
- 代码实现
def balancedString(s):
"""
:type s: str
:rtype: int
"""
# 这个函数就是实现上面分析的第四步
# len表示窗口的大小，也就是有len个元素可以替换，看能不能使窗口外面的每种字符出现次数达到aver
def ok(cnts, len, aver):
for i in range(4):
if cnts[i] > aver:
return False
len -= aver - cnts[i]
return True if len == 0 else False
n = len(s)
aver = n // 4
# 将Q映射成0，W映射成1，E映射成2，R映射成3
data = ['Q', 'W', 'E', 'R']
cnts = [0] * 4
for i in range(n):
cnts[data.index(s[i])] += 1
# 作为替换字串的最小长度返回
ans = n
r = 0
# 左窗口开始遍历s
for l in range(n):
# l-r表示[l,r)范围
# 如果当前窗口不行，右窗口ji
while ok(cnts, r - l, aver) == False and r < n:
# 右窗口每次向右移动都会在窗口内新加入一个字符，它在窗口外的出现次数要减1
cnts[data.index(s[r])] -= 1
r += 1
# 这里是为了判断上面循环是因为第一个条件结束还是因为第二个条件结束的
# 若是因为第二个条件结束的，就说明这个窗口是合法的，当然这里只能判断第一个条件
# 因为第一个条件也有可能不符合
if r != n:
ans = min(ans, r - l)
# 最后一次循环结束后，左窗口会向右移动，相当于会将它原来所在位置的字符排除到窗口外，所以在窗口外这个字符的出现次数要加1
cnts[data.index(s[l])] += 1
return ans
