第十六关 | 经典刷题思想之滑动窗口：2.白银挑战—滑动窗口经典问题-灵析社区
时光小少年1. 最长子串专题
先来看一道高频算法题：无重复字符的最长子串。具体要求是给定一个字符串 s ，请你找出其中不含有重复字符的最长子串的长度。例如，输入: s = "abcabcbb" 则输出3，因为无重复字符的最长子串是 "abc"，所以其长度为3。
怎么做后面再说，如果再变一下要求，至多包含两个不同字符的最长子串，该怎么做呢？
再变一下要求，至多包含 K 个不同字符的最长子串，该怎么做呢？
到这里是否感觉，这不在造题吗？是的！上面就分别是LeetCode3、159、340题，而且这几道题都可以用滑动窗口来解决。学会之后，我们就总结出滑动窗口的解题模板了。
接下来，我们就一道一道看。
1.1. 无重复字符的最长子串
LeetCode3 给定一个字符串 s ，请你找出其中不含有重复字符的最长子串的长度。例如：
输入: s = "abcabcbb"
输出: 3
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。
要找最长子串，必然要知道无重复字符串的首和尾，然后再从中确定最长的那个，因此至少两个指针才可以，这就想到了滑动窗口思想。即使使用滑动窗口，深入分析会发现具体处理起来有多种方式。这里介绍一种经典的使用Map的思路。
我们定义一个K-V形式的map，key表示的是当前正在访问的字符串，value是其下标索引值。我们每访问一个新元素，都将其下标更新成对应的索引值。具体过程如下图：
如果是已经出现过的，例如上述示例中的 abcabc，当第二次遇到a时，我们就更新left成为第一个b所在的位置，此时惊奇的发现left要移动的位置恰好就是map.get(’a‘) + 1=1，我们将'a'用序列来表示，放在一起就是map.get(s.charAt(i)) + 1。其他情况可以参考图示依次类推。
有一种特殊情况我们需要考虑，例如abba，我们第二次访问b时，left=map.get(’b‘) + 1=2。
然后继续访问第二个a，此时left=map.get(’a‘) + 1=1，也就是left后退了，显然不对。
我们应该让left在2的基础上继续向前，那该怎么办呢？和原来的对比一下，将最大的加1就可以了，也就是：
left = Math.max(left,map.get(s.charAt(i)) + 1);
完整的代码如下：
public int lengthOfLongestSubstring(String s) {
if (s.length() == 0) return 0;
HashMap<Character, Integer> map = new HashMap<Character, Integer>();
int max = 0;
int left = 0;
for (int right = 0; right < s.length(); right++) {
if (map.containsKey(s.charAt(right))) {
left = Math.max(left, map.get(s.charAt(right)) + 1);
}
map.put(s.charAt(right), right);
max = Math.max(max, right - left + 1);
}
return max;
}
def lengthOfLongestSubstring(self, s):
if not s:
return 0
left = 0
lookup = set()
n = len(s)
max_len = 0
cur_len = 0
for i in range(n):
cur_len += 1
while s[i] in lookup:
lookup.remove(s[left])
left += 1
cur_len -= 1
if cur_len > max_len:
max_len = cur_len
lookup.add(s[i])
return max_len
int lengthOfLongestSubstring(std::string s) {
if (s.empty()) return 0;
std::unordered_map<char, int> map;
int max = 0;
int left = 0;
for (int right = 0; right < s.length(); right++) {
if (map.count(s[right]) > 0) {
left = std::max(left, map[s[right]] + 1);
}
map[s[right]] = right;
max = std::max(max, right - left + 1);
}
return max;
}
除了上述方法，不用Hash存储索引，也可以用滑动窗口思想来解决，感兴趣的可以研究一下。
1.2. 至多包含两个不同字符的最长子串
给定一个字符串 s ，找出 至多 包含两个不同字符的最长子串 t ，并返回该子串的长度，这就是LeetCode159题。例如：
输入: "eceba"
输出: 3
解释: t 是 "ece"，长度为3。
.我们仍然使用left和right来锁定一个窗口，然后一边向右移动一边分析。我们用一个序列来看一下：aabbcccd。
我们接下来需要解决两个问题，一个是怎么判断只有2个元素，另一个是移除的时候怎么知道移除谁，以及移除之后left是什么。
要判断只有2个元素，还是Hash好用，每一个时刻，这个 hashmap 包括不超过 3 个元素。这里还要考虑到要移除谁，所以我们要设计一下Hash的Key-Value的含义。我们把字符串里的字符都当做键，在窗口中的最右边的字符位置作为值。此时使用下面的代码就可以确定要删除谁，以及窗口left的新位置：
del_idx = Collections.min(hashmap.values());
left = del_idx + 1;
为什么呢？我们还是画图看一下：
所以我们可以充分利用Map的工具来解决该问题：
public int lengthOfLongestSubstringTwoDistinct(String s) {
if (s.length() < 3) {
return s.length();
}
int left = 0, right = 0;
HashMap<Character, Integer> hashmap = new HashMap<>();
int maxLen = 2;
while (right < s.length()) {
if (hashmap.size() < 3)
hashmap.put(s.charAt(right), right++);
// 如果大小达到了3个
if (hashmap.size() == 3) {
// 最左侧要删除的位置
int del_idx = Collections.min(hashmap.values());
hashmap.remove(s.charAt(del_idx));
// 窗口left的新位置
left = del_idx + 1;
}
maxLen = Math.max(maxLen, right - left);
}
return maxLen;
}
def lengthOfLongestSubstringTwoDistinct(self, s):
n = len(s)
if n < 3:
return n
left, right = 0, 0
hashmap = defaultdict()
max_len = 2
while right < n:
if len(hashmap) < 3:
hashmap[s[right]] = right
right += 1
if len(hashmap) == 3:
del_idx = min(hashmap.values())
del hashmap[s[del_idx]]
left = del_idx + 1
max_len = max(max_len, right - left)
return max_len
int lengthOfLongestSubstringTwoDistinct(std::string s) {
int n = s.length();
if (n < 3) {
return n;
}
int left = 0, right = 0;
std::unordered_map<char, int> hashmap;
int max_len = 2;
while (right < n) {
if (hashmap.size() < 3) {
hashmap[s[right]] = right;
right++;
} else {
int del_idx = *std::min_element(hashmap.begin(), hashmap.end());
hashmap.erase(del_idx);
left = del_idx + 1;
}
max_len = std::max(max_len, right - left + 1);
}
return max_len;
}
1.3. 至多包含 K 个不同字符的最长子串
如果再提高一下难度， 至多包含 K 个不同字符的最长子串该怎么办呢？这就是LeetCode340题。
题目的完整要求是：给定一个字符串 s，找出 至多 包含 k 个不同字符的最长子串T。示例：
输入: s = "eceba", k = 2
输出: 3
解释: 则 T 为 "ece"，所以长度为 3。
本题与上面的题几乎没有区别，只要将判断hash大小为2改成k就可以，超过2就是k+1。十分钟实现：
public int lengthOfLongestSubstringKDistinct(String s, int k) {
if (s.length() < k + 1) {
return s.length();
}
int left = 0, right = 0;
HashMap<Character, Integer> hashmap = new HashMap<>();
int maxLen = k;
while (right < s.length()) {
if (hashmap.size() < k + 1)
hashmap.put(s.charAt(right), right++);
// 如果大小达到了k个
if (hashmap.size() == k + 1) {
int del_idx = Collections.min(hashmap.values());
hashmap.remove(s.charAt(del_idx));
// 窗口left的新位置
left = del_idx + 1;
}
maxLen = Math.max(maxLen, right - left);
}
return maxLen;
}
def lengthOfLongestSubstringKDistinct(self, s, k):
n = len(s)
if k == 0 or n == 0:
return 0
left, right = 0, 0
hashmap = defaultdict()
max_len = 1
while right < n:
hashmap[s[right]] = right
right += 1
if len(hashmap) == k + 1:
del_idx = min(hashmap.values())
del hashmap[s[del_idx]]
left = del_idx + 1
max_len = max(max_len, right - left)
return max_len
int lengthOfLongestSubstringKDistinct(std::string s, int k) {
if (s.length() < k + 1) {
return s.length();
}
int left = 0, right = 0;
std::unordered_map<char, int> hashmap;
int maxLen = k;
while (right < s.length()) {
if (hashmap.size() < k + 1) {
hashmap[s[right]] = right++;
}
// 如果大小达到了k个
if (hashmap.size() == k + 1) {
// 找到最小的值并删除，更新窗口左边界
int del_idx = *std::min_element(hashmap.begin(), hashmap.end());
hashmap.erase(s[del_idx]);
left = del_idx + 1;
}
maxLen = std::max(maxLen, right - left);
}
return maxLen;
}
2. 长度最小的子数组
LeetCode209.长度最小的子数组,给定一个含有 n 个正整数的数组和一个正整数 target 。
找出该数组中满足其和 ≥ target 的长度最小的 连续子数组 [numsl, numsl+1, ..., numsr-1, numsr] ，并返回其长度。如果不存在符合条件的子数组，返回 0 。
输入：target = 7, nums = [2,3,1,2,4,3]
输出：2
解释：子数组 [4,3] 是该条件下的长度最小的子数组。
本题可以使用双指针来解决，也可以视为队列法，基本思路是先让元素不断入队，当入队元素和等于target时就记录一下此时队列的容量，如果队列元素之和大于target则开始出队， 直到小于target则再入队。
如果出现等于target的情况，则记录一下此时队列的大小，之后继续先入队再出队。每当出现元素之和等于target时我们就保留容量最小的那个。
实现代码如下：
public int minSubArrayLen(int target, int[] nums) {
int left = 0, right = 0, sum = 0, min = Integer.MAX_VALUE;
while (right < nums.length) {
sum += nums[right++];
while (sum >= target) {
min = Math.min(min, right - left);
sum -= nums[left++];
}
}
return min == Integer.MAX_VALUE ? 0 : min;
}
def minSubArrayLen(self, s, nums):
if not nums:
return 0
n = len(nums)
ans = n + 1
start, end = 0, 0
total = 0
while end < n:
total += nums[end]
while total >= s:
ans = min(ans, end - start + 1)
total -= nums[start]
start += 1
end += 1
return 0 if ans == n + 1 else ans
int minSubArrayLen(int target, int* nums, int numsSize) {
int left = 0, right = 0, sum = 0, min = INT_MAX;
while (right < numsSize) {
sum += nums[right++];
while (sum >= target) {
min = std::min(min, right - left);
sum -= nums[left++];
}
}
return min == INT_MAX ? 0 : min;
}
3. 盛水最多的容器
LeetCode11.给定一个长度为 n 的整数数组 height 。有 n 条垂线，第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。返回容器可以储存的最大水量。
示例：
输入：[1,8,6,2,5,4,8,3,7]
输出：49
解释：图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]。在此情况下，容器能够容纳水（表示为蓝色部分）的最大值为 49。
本题看似复杂，但其实简单的很。设两指针 i , j ，指向的水槽板高度分别为 h[i] , h[j] ，此状态下水槽面积为S(i,j) 。由于可容纳水的高度由两板中的 短板 决定，因此可得如下面积公式 ：
S(i,j)=min(h[i],h[j])×(j−i)
在每个状态下，无论长板或短板向中间收窄一格，都会导致水槽底边宽度−1 变短：
- 若向内移动短板 ，水槽的短板min(h[i],h[j]) 可能变大，因此下个水槽的面积可能增大 。
- 若向内移动长板 ，水槽的短板min(h[i],h[j]) 不变或变小，因此下个水槽的面积一定变小 。
因此，只要初始化双指针分列水槽左右两端，循环每轮将短板向内移动一格，并更新面积最大值，直到两指针相遇时跳出；即可获得最大面积。
public int maxArea(int[] height) {
int i = 0, j = height.length - 1, res = 0;
while(i < j) {
res = height[i] < height[j] ?
Math.max(res, (j - i) * height[i++]):
Math.max(res, (j - i) * height[j--]);
}
return res;
}
def maxArea(self, height):
i, j, res = 0, len(height) - 1, 0
while i < j:
if height[i] < height[j]:
res = max(res, height[i] * (j - i))
i += 1
else:
res = max(res, height[j] * (j - i))
j -= 1
return res
int maxArea(int* height, int heightSize) {
int i = 0, j = heightSize - 1, res = 0;
while (i < j) {
res = std::max(res, std::max(height[i], height[j]) * (j - i));
if (height[i] > height[j]) {
i++;
} else {
j--;
}
}
return res;
}
4. 寻找子串异位词（排列）
如果两个字符串仅仅是字母出现的位置不一样，则称两者相互为对方的一个排列，也称为异位词。
如果判断两个字符串是否互为排列，是字符串的一个基本算法。现在我们给增加难度。看LeetCode567和438两个题。
4.1. 字符串的排列
LeetCode567.给你两个字符串s1和s2 ，写一个函数来判断 s2是否包含 s1的排列。如果是，返回 true ；否则，返回 false 。换句话说，s1 的排列之一是 s2 的子串 。其中s1和s2都只包含小写字母。
示例：
输入：s1 = "ab" s2 = "eidbaooo"
输出：true
解释：s2 包含 s1 的排列之一 ("ba").
本题因为字符串s1的异位词长度一定是和s2字符串的长度一样的，所以很自然的想到可以以s1.length()为大小截图一个固定窗口，然后窗口一边向右移动，一边比较就行了。此时可以将窗口内的元素和s1先做一个排序，然后再比较即可，但是这样做的问题是排序代价太高了，我们需要考虑性能更优的方法。
所谓的异位词不过两点：字母类型一样，每个字母出现的个数也是一样的。题目说s1和s2都仅限小写字母，因此我们可以创建一个大小为26的数组，每个位置就存储从a到z的个数，为了方便操作，索引我们使用
index=s1.charAt(i) - 'a'
来表示，这是处理字符串的常用技巧。
此时窗口的right向右移动就是执行：
charArray2[s2.charAt(right) - 'a']++;
而left向右移动就是执行：
int left = right - sLen1;
charArray2[s2.charAt(left) - 'a']--;
所以，完整代码如下：
public boolean checkInclusion(String s1, String s2) {
int sLen1 = s1.length(), sLen2 = s2.length();
if (sLen1 > sLen2) {
return false;
}
int[] charArray1 = new int[26];
int[] charArray2 = new int[26];
//先读最前面的一段来判断。
for (int i = 0; i < sLen1; ++i) {
++charArray1[s1.charAt(i) - 'a'];
++charArray2[s2.charAt(i) - 'a'];
}
if (Arrays.equals(charArray1, charArray2)) {
return true;
}
for (int right = sLen1; right < sLen2; ++right) {
charArray2[s2.charAt(right) - 'a']++;
int left = right - sLen1;
charArray2[s2.charAt(left) - 'a']--;
if (Arrays.equals(charArray1, charArray2)) {
return true;
}
}
return false;
}
def checkInclusion(self, s1, s2):
n = len(s1)
n2 = len(s2)
dic1 = {}
for i in s1:
if i not in dic1:
dic1[i] = 1
else:
dic1[i] += 1
for i in range(n2 - n + 1):
dic2 = {}
for j in s2[i:i + n]:
if j not in dic2:
dic2[j] = 1
else:
dic2[j] += 1
if dic2 == dic1:
return True
return False
bool checkInclusion(string s1, string s2) {
int n = s1.length(), m = s2.length();
if (n > m) {
return false;
}
vector<int> cnt1(26), cnt2(26);
for (int i = 0; i < n; ++i) {
++cnt1[s1[i] - 'a'];
++cnt2[s2[i] - 'a'];
}
if (cnt1 == cnt2) {
return true;
}
for (int i = n; i < m; ++i) {
++cnt2[s2[i] - 'a'];
--cnt2[s2[i - n] - 'a'];
if (cnt1 == cnt2) {
return true;
}
}
return false;
}
4.2. 找到字符串中所有字母异位
LeetCode438.找到字符串中所有字母异位词，给定两个字符串 s 和 p，找到 s 中所有 p 的 异位词 的子串，返回这些子串的起始索引。不考虑答案输出的顺序。注意s和p仅包含小写字母。
异位词 指由相同字母重排列形成的字符串（包括相同的字符串）。例如：
输入: s = "cbaebabacd", p = "abc"
输出: [0,6]
解释:
起始索引等于 0 的子串是 "cba", 它是 "abc" 的异位词。
起始索引等于 6 的子串是 "bac", 它是 "abc" 的异位词。
本题的思路和实现与上面几乎一模一样，唯一不同的是需要用一个List，如果出现异位词，还要记录其开始位置，那直接将其add到list中就可以了。完整代码：
public List<Integer> findAnagrams(String s, String p) {
int sLen = s.length(), pLen = p.length();
if (sLen < pLen) {
return new ArrayList<Integer>();
}
List<Integer> ans = new ArrayList<Integer>();
int[] sCount = new int[26];
int[] pCount = new int[26];
//先分别初始化两个数组
for (int i = 0; i < pLen; i++) {
sCount[s.charAt(i) - 'a']++;
pCount[p.charAt(i) - 'a']++;
}
if (Arrays.equals(sCount, pCount)) {
ans.add(0);
}
for (int left = 0; left < sLen - pLen; left++) {
sCount[s.charAt(left) - 'a']--;
int right=left + pLen;
sCount[s.charAt(right) - 'a']++;
if (Arrays.equals(sCount, pCount)) {
//上面left多减了一次，所以
ans.add(left + 1);
}
}
return ans;
}
def findAnagrams(self, s, p):
s_len, p_len = len(s), len(p)
if s_len < p_len:
return []
ans = []
s_count = [0] * 26
p_count = [0] * 26
for i in range(p_len):
s_count[ord(s[i]) - 97] += 1
p_count[ord(p[i]) - 97] += 1
if s_count == p_count:
ans.append(0)
for i in range(s_len - p_len):
s_count[ord(s[i]) - 97] -= 1
s_count[ord(s[i + p_len]) - 97] += 1
if s_count == p_count:
ans.append(i + 1)
return ans
vector<int> findAnagrams(string s, string p) {
int sLen = s.size(), pLen = p.size();
if (sLen < pLen) {
return vector<int>();
}
vector<int> ans;
vector<int> sCount(26);
vector<int> pCount(26);
for (int i = 0; i < pLen; ++i) {
++sCount[s[i] - 'a'];
++pCount[p[i] - 'a'];
}
if (sCount == pCount) {
ans.emplace_back(0);
}
for (int i = 0; i < sLen - pLen; ++i) {
--sCount[s[i] - 'a'];
++sCount[s[i + pLen] - 'a'];
if (sCount == pCount) {
ans.emplace_back(i + 1);
}
}
return ans;
}阅读量：790
点赞量：0
收藏量:0