看一下上一篇留下的那个题目：
LeetCode 209:Minimum Size Subarray Sum
给定一个整型数组和一个数字S，找到数组中的一个连续子数组，使得连续子数组的数值之和sum>=S，返回此最短的连续子数组的长度。
- 如给定数组[2,3,1,2,4,3],S=7
- 答案为[4,3]，返回2. 如果无解，返回0.
首先，如果一开始没有想到好的解法，那么可以考虑采用暴力解法：即遍历所有的连续子数组[i...j]，计算其sum和，验证sum>=S。
使用暴力解法的时间复杂度为O(N3)。
但是暴力解法包含了大量的重复计算，它会对已经计算过的结果，在下一次遍历的时候又再进行一次计算。
为了解决这个问题，可以这样考虑：
- 首先使用i和j分别指向一段数组中的一段数据，即nums[i]~nums[j]。
- 如果nums[i]~nums[j]这个数据段里的和小于S，那么就把j的值+1，即向后多看一个数据，检查是否仍然小于S，如果小于，则继续这么做。
- 如果nums[i]nums[j]这个数据段的和大于S了，则记下此时ij的元素个数Min并且与之前记录的最短长度比对后取最小值，然后把i的值+1，即将数据段缩小一位，再进行检查。直到i的值到数组末尾为止。
- 这样最后得到的Min即为最短的连续子数组的长度。
在这个解法中，由i ~ j维持了一个不断变化的滑动窗口，时间复杂度为O(N)。利用这种方法，可以求解很多问题。下面是此题的具体实现：
int minSubArrayLen(int s, vector<int>& nums) {
// l~r即为我们要构造的滑动窗口，r=-1表示一开始还没有此窗口
int l = 0;
int r = -1;
int sum = 0;
int length = nums.size() + 1;
while(l < nums.size()) {
//别忘记判断r数组越界
if(sum < s && r < nums.size() - 1) {
sum += nums[++r];
} else {
sum -= nums[l++];
}
if(sum >= s) {
length = min(length, r-l+1);
}
}
if(length == nums.size() + 1)
return 0;
else
return length;
}
掌握了滑动窗口之后，再来看一下LeetCode上的另外一道与之相关的题目。
LeetCode 3 Longest SubString Without Repeating Characters
在字符串中寻找没有重复字母的最长子串
- 如“abcabcab”，返回3，abc
- 如“pwwkew”，返回3，wke/kew
使用滑动窗口解此题目的方法如下：
- 使用i和j构造一个滑动窗口
- 对于每次窗口增大(即j++)时，判断进入窗口的元素是否在滑动窗口内出现过，如果没出现，则将窗口增大一位。
- 在增大窗口时，如果窗口里已经有此元素了，那么就把i的值-1，即缩小一下窗口，直到窗口内没有出现此元素。
- 每次记录滑动窗口最大到过多少，然后返回即可
在这里，有一个小细节，如何判断即将进入的元素是否在滑动窗口中出现过？总不能一一比较吧。
这里有一个比较简单的思路是设置一个字符数组freq[256]，存储所有的字符，它的值代表每个字符出现的次数。算法代码如下：
int lengthOfLongestSubstring(string s) {
if(s.size() == 0) {
return 0;
}
int freq[256] = {0};
int l = 0, r= -1;
int res = 0;
while (l < s.size()) {
if(r+1 < s.size() && freq[s[r+1]] == 0)
freq[s[++r]] ++;
else
freq[s[l++]] -- ;
res = max(res, r-l+1);
}
return res;
}
对于这个看起来复杂的问题，解决的代码却很简单。关键在于思路是正确且清晰的，这样就能快速地找到解决办法。
下面是一些与之相关的题目可供练习，代码和思路照例会在下一篇中给出。大家有问题请给我留言评论。
LeetCode438 Find All Anagrams in a String
给定一个字符串S和一个非空字符串P，找出P中的所有是S的anagrams字符串的子串并返回这些子串的起始索引。
- 如S = "cbaebabacd",P="abc",返回[0,6]。
- 如S = "abab",P = "ba",返回[0,1,2]。
注：anagrams字符串指字母相同，顺序不同。
LeetCode76 Minimum Window SubString
给定一个字符串S和T，在S中寻找最短的子串，包含T中的所有字符。
- 如：S = "ADOBECODEBANC"; T = "ABC"
- 结果为"BANC"
注：这是一道难度为hard的题目。
至此，数组阶段就已经结束了。在后面的文章中，将会介绍查找这种面试中同样常见的问题。希望大家继续关注。
网友评论