例题1：LeetCode 第 209 题：长度最小的子数组
传送门：英文网址：209. Minimum Size Subarray Sum ，中文网址：209. 长度最小的子数组 。
给定一个含有 n 个正整数的数组和一个正整数 s ，找出该数组中满足其和 ≥ s 的长度最小的连续子数组。如果不存在符合条件的连续子数组，返回 0。
示例:
输入: s = 7, nums = [2,3,1,2,4,3] 输出: 2 解释: 子数组 [4,3] 是该条件下的长度最小的连续子数组。进阶:
如果你已经完成了O(n) 时间复杂度的解法, 请尝试 O(n log n) 时间复杂度的解法。
思路1：使用滑动窗口的技巧来完成，要看过一遍整个数组的元素，时间复杂度是 。要求满足区间和 >= s 的最小子区间的长度，因此，我们从左向右进行扫描。
情况1：当区间和小于 s 的时候，右区间的端点向右扩展，这一点依赖外层循环的遍历就可以完成；
情况2：一旦区间和大于等于 s，尝试一步一步缩小左区间端点，看看是否能得到一个更短的区间，满足区间和 >=s，这一步通过一个内层循环实现。
Python 代码1：在理解的基础上，记住下面这个写法，右指针也是用于遍历的指针
class Solution:
def minSubArrayLen(self, s, nums):
"""
:type s: int
:type nums: List[int]
:rtype: int
"""
# 滑动窗口
size = len(nums)
# 特判
if size == 0:
return 0
l = 0
# 既然是求最小的长度，初始值应该设置成一个不可能达到的上限
res = size + 1
cur_sum = 0
for i in range(size):
cur_sum += nums[i]
# 此时 cur_sum >= s
while cur_sum >= s:
res = min(res, i - l + 1)
cur_sum -= nums[l]
l += 1
# 如果全部数组元素加起来都 < s ，即 res 的值没有被更新，根据题意返回 0
if res == len(nums) + 1:
return 0
return res
Python 代码2：
class Solution:
def minSubArrayLen(self, s, nums):
"""
:type s: int
:type nums: List[int]
:rtype: int
"""
# 滑动窗口
size = len(nums)
# 特判
if size == 0:
return 0
l = 0
r = -1
sum = 0
res = size + 1
while l < size:
if r + 1 < size and sum < s:
r += 1
sum += nums[r]
else:
sum -= nums[l]
l += 1
if sum >= s:
res = min(res, r - l + 1)
if res == size + 1:
return 0
return res
Java 代码：使用滑动窗口
public class Solution {
public int minSubArrayLen(int s, int[] nums) {
int len = nums.length;
if (len == 0) {
return 0;
}
int l = 0;
int r = 0;
int minSubArrayLen = len + 1;
int segmentSum = 0;
for (int num : nums) {
segmentSum += num;
r++;
// 注意：根据题意"找出该数组中满足其和 ≥ s 的长度最小的子数组"
// 注意这个边界条件
while (segmentSum >= s) {
minSubArrayLen = Integer.min(minSubArrayLen, r - l);
segmentSum -= nums[l];
l++;
}
}
if (minSubArrayLen == len + 1) {
return 0;
}
return minSubArrayLen;
}
}
思路2：二分法，利用“数组是正整数”这个条件，构造前缀和数组，这个前缀和数组一定是严格增加的。 任意区间和可以通过前缀和数组得到，这是我们常见的一种做法。 起点固定的时候，区间越长，区间和越大。
Java 代码：构造前缀和数组，使用二分查找法，要考虑一些边界条件，编码易出错，了解即可
public class Solution {
public int minSubArrayLen(int s, int[] nums) {
int len = nums.length;
if (len == 0) {
return 0;
}
// 构造前缀和数组
// 因为 nums 全都是正整数，因此 preSum 严格单调增加
int[] preSum = new int[len];
preSum[0] = nums[0];
for (int i = 1; i < len; i++) {
preSum[i] = preSum[i - 1] + nums[i];
}
// 因为前缀和数组严格单调增加，因此我们可以使用二分查找算法
// 最后一位没有下一位了，所以外层遍历到最后一位的前一位就可以了
int ret = len + 1;
for (int i = 0; i < len - 1; i++) {
// 计算区间和
int l = i;
int r = len - 1;
// 设置成一个比较大的数，但是这个数有下界
// i 的最大值是 len - 2,
// ans - i + 1 >= len + 1
// ans >= i + len = 2 * len -2
int ans = 2 * len - 2;
// int ans = 2 * len - 1; 能通过
// int ans = 2 * len - 3; 不能通过
// 退出循环的条件是 l > r
while (l <= r) {
int mid = l + (r - l) / 2;
// 计算一下区间和，找一个位置，使得这个位置到索引 i 的区间和为 s
// 13 14 15 17 19 20
int segmentSum = preSum[mid] - (i == 0 ? 0 : preSum[i - 1]);
if (segmentSum >= s) {
ans = mid;
r = mid - 1;
} else {
l = mid + 1;
}
}
ret = Integer.min(ans - i + 1, ret);
}
if (ret == len + 1) {
return 0;
}
return ret;
}
}
练习1：LeetCode 第 438 题：找到字符串中所有字母异位词（典型问题）
传送门：英文网址：438. Find All Anagrams in a String ，中文网址：438. 找到字符串中所有字母异位词 。
给定一个字符串 s 和一个非空字符串 p，找到 s 中所有是 p 的字母异位词的子串，返回这些子串的起始索引。
字符串只包含小写英文字母，并且字符串 s 和 p 的长度都不超过 20100。
说明：
- 字母异位词指字母相同，但排列不同的字符串。
- 不考虑答案输出的顺序。
示例 1:
输入: s: "cbaebabacd" p: "abc" 输出: [0, 6] 解释: 起始索引等于 0 的子串是 "cba", 它是 "abc" 的字母异位词。 起始索引等于 6 的子串是 "bac", 它是 "abc" 的字母异位词。示例 2:
输入: s: "abab" p: "ab" 输出: [0, 1, 2] 解释: 起始索引等于 0 的子串是 "ab", 它是 "ab" 的字母异位词。 起始索引等于 1 的子串是 "ba", 它是 "ab" 的字母异位词。 起始索引等于 2 的子串是 "ab", 它是 "ab" 的字母异位词。
说明：这是一道使用滑动窗口解决的典型问题。虽然标记为简单，但是也不好做。
思路1：滑动窗口的右边界划过的时候，map 对应的次数减少，左边界划过的时候，map 对应的次数增加。设置一个 distance 变量，表示二者的差距。
Python 代码：在理解的基础上，记住这个解法
class Solution:
def findAnagrams(self, s, p):
"""
:type s: str
:type p: str 模式串
:rtype: List[int]
"""
from collections import defaultdict
hash = defaultdict(int)
# 滑动窗口的长度
plen = len(p)
# 预处理
for alpha in p:
hash[alpha] += 1
# 滑动窗口的左边界
l = 0
# 滑动窗口的右边界
r = 0
res = []
# 可以认为是两者的差距
distance = plen
while r < len(s):
if hash[s[r]] > 0:
distance -= 1
hash[s[r]] -= 1
r += 1
if distance == 0:
res.append(l)
if r - l == plen:
if hash[s[l]] >= 0:
distance += 1
hash[s[l]] += 1
l += 1
return res
if __name__ == '__main__':
s = "cbaebabacd"
p = "abc"
solution = Solution()
result = solution.findAnagrams(s, p)
print(result)
思路2：（参考）给 p 做字母频率统计，扫过以后，全部一样，就表示找到一个字母异位词。
Python 代码：
class Solution:
def findAnagrams(self, s, p):
"""
:type s: str
:type p: str
:rtype: List[int]
"""
plen = len(p)
slen = len(s)
scnt = [0] * 26
pcnt = [0] * 26
res = []
for alpha in p:
pcnt[ord(alpha) - ord('a')] += 1
for end in range(slen):
if end >= plen:
scnt[ord(s[end - plen]) - ord('a')] -= 1
scnt[ord(s[end]) - ord('a')] += 1
if scnt == pcnt:
res.append(end - plen + 1)
return res
if __name__ == '__main__':
s = "cbaebabacd"
p = "abc"
solution = Solution()
result = solution.findAnagrams(s, p)
print(result)
Python 代码：与上一版代码等价
class Solution:
def findAnagrams(self, s, p):
"""
:type s: str
:type p: str
:rtype: List[int]
"""
# 滑动窗口的大小
plen = len(p)
slen = len(s)
scnt = [0] * 26
pcnt = [0] * 26
res = []
for alpha in p:
pcnt[ord(alpha) - ord('a')] += 1
for end in range(slen):
scnt[ord(s[end]) - ord('a')] += 1
if end >= plen - 1:
if scnt == pcnt:
res.append(end - plen + 1)
scnt[ord(s[end - plen + 1]) - ord('a')] -= 1
return res
Java 代码：
import java.util.ArrayList;
import java.util.List;
public class Solution5 {
// 这种解法从语义上更好理解一些
public List<Integer> findAnagrams(String s, String p) {
List<Integer> res = new ArrayList<>();
int[] cntp = new int[26];
int[] cnts = new int[26];
int plen = p.length();
int slen = s.length();
// 数组 cntp 在预处理以后是不会
for (int i = 0; i < plen; i++) {
cntp[p.charAt(i) - 'a']++;
}
// 数 0 的个数
int same = 0;
for (int i = 0; i < 26; i++) {
if (cntp[i] == 0) {
same++;
}
}
for (int i = 0; i < slen; i++) {
// 右边界进来的时候全部加 1
char curChar = s.charAt(i);
cnts[curChar - 'a']++;
if (cnts[curChar - 'a'] == cntp[curChar - 'a']) {
// 右边界进来的时候，正好相等，则两个数组相同的数量加 1
same++;
} else if (cnts[curChar - 'a'] == cntp[curChar - 'a'] + 1) {
// 右边界进来的时候，s 数组比 p 数组相应位置多 1，也就是说，二者不等，所以相同的数量减 1
same--;
}
if (i >= plen) {
// 计算左边界
int deleteIndex = i - plen;
char deleteChar = s.charAt(deleteIndex);
// 左边界出来的时候，全部减 1
cnts[deleteChar - 'a']--;
if (cnts[deleteChar - 'a'] == cntp[deleteChar - 'a']) {
// 滑出去以后相等，所以加 1
same++;
} else if (cnts[deleteChar - 'a'] == cntp[deleteChar - 'a'] - 1) {
// 滑出去以后，比数组 p 少 1，所以减 1
same--;
}
}
if (same == 26) {
res.add(i - plen + 1);
}
}
return res;
}
}
练习2：LeetCode 第 76 题：最小覆盖子串
传送门：英文网址：76. Minimum Window Substring ，中文网址：76. 最小覆盖子串 。
给定一个字符串 S 和一个字符串 T，请在 S 中找出包含 T 所有字母的最小子串。
示例：
输入: S = "ADOBECODEBANC", T = "ABC" 输出: "BANC"说明：
- 如果 S 中不存这样的子串，则返回空字符串
""。- 如果 S 中存在这样的子串，我们保证它是唯一的答案。
说明：这道题被 LeetCode 标记为“困难”。
Java 代码：
import java.util.HashSet;
import java.util.Set;
public class Solution {
// 参考资料：https://blog.csdn.net/feliciafay/article/details/44535301
// 先复习第 438 题再做这题可能会好些
// 滑动窗口，这个问题有一些难
public String minWindow(String s, String t) {
int[] cntS = new int[256];
int[] cntT = new int[256];
Set<Character> set = new HashSet<>();
// cntT 赋值了以后，就成为了用于比对的对象，不更新
for (char ct : t.toCharArray()) {
cntT[ct]++;
set.add(ct);
}
int minSub = s.length() + 1;
String res = "";
// 滑动窗口左边界
int left = 0;
// 滑动窗口右边界
int right = 0;
// 逻辑：右边界进来的时候，数组 s 的次数都加 1
int count = 0;
while (right < s.length()) {
char rc = s.charAt(right);
if (!set.contains(rc)) {
// 不在字典里面，但是右边界同样要扩充，所以 right++
right++;
continue;
}
cntS[rc]++;
right++;
// 理解这里是关键：加上以后，小于等于，count 才 ++，
if (cntS[rc] <= cntT[rc]) {
// count++; 这件事情说明滑动窗口里面的有效字符，向目标字符又近了一步
count++;
}
// 下面这一段可以写得更精简一些，但是为了语义上的清晰，我就写得冗长一些
if (count == t.length()) {
// 接下来，考虑左边界移出滑动窗口
// 不在字典中，或者多了的时候，直接划掉就可以了
while (true) {
char deleteChar = s.charAt(left);
if (!set.contains(deleteChar)) {
left++;
continue;
}
if (cntS[deleteChar] > cntT[deleteChar]) {
cntS[deleteChar]--;
left++;
continue;
}
break;
}
if (right - left < minSub) {
minSub = right - left;
res = s.substring(left, right);
}
}
}
if (minSub == s.length() + 1) {
return "";
}
return res;
}
public static void main(String[] args) {
Solution solution = new Solution();
String S = "ADOBECODEBANC";
String T = "ABC";
String minWindow = solution.minWindow(S, T);
System.out.println(minWindow);
}
}
参考资料：https://blog.csdn.net/feliciafay/article/details/44535301
https://blog.csdn.net/u013115610/article/details/70257445
（本节完）
网友评论