3. 无重复字符的最长子串
滑动窗口
我们先用一个例子考虑如何在较优的时间复杂度内通过本题。
我们不妨以示例一中的字符串 abcabcbb 为例，找出从每一个字符开始的，不包含重复字符的最长子串，那么其中最长的那个字符串即为答案。对于示例一中的字符串，我们列举出这些结果，其中括号中表示选中的字符以及最长的字符串：
以 (a)bcabcbb 开始的最长字符串为 (abc)abcbb；
以 a(b)cabcbb 开始的最长字符串为 a(bca)bcbb；
以 ab(c)abcbb 开始的最长字符串为 ab(cab)cbb；
以 abc(a)bcbb 开始的最长字符串为 abc(abc)bb；
以 abca(b)cbb 开始的最长字符串为 abca(bc)bb；
以 abcab(c)bb 开始的最长字符串为 abcab(cb)b；
以 abcabc(b)b 开始的最长字符串为 abcabc(b)b；
以 abcabcb(b) 开始的最长字符串为 abcabcb(b)。
发现了什么？如果我们依次递增地枚举子串的起始位置，那么子串的结束位置也是递增的！这里的原因在于，假设我们选择字符串中的第 k 个字符作为起始位置，并且得到了不包含重复字符的最长子串的结束位置为 rk。那么当我们选择第 k+1 个字符作为起始位置时，首先从 k+1 到 rk的字符显然是不重复的，并且由于少了原本的第 k 个字符，我们可以尝试继续增大 rk，直到右侧出现了重复字符为止。这样一来，我们就可以使用「滑动窗口」来解决这个问题了：
我们使用两个指针表示字符串中的某个子串（或窗口）的左右边界，其中左指针代表着上文中「枚举子串的起始位置」，而右指针即为上文中的 rk；在每一步的操作中，我们会将左指针向右移动一格，表示 我们开始枚举下一个字符作为起始位置，然后我们可以不断地向右移动右指针，但需要保证这两个指针对应的子串中没有重复的字符。在移动结束后，这个子串就对应着 以左指针开始的，不包含重复字符的最长子串。我们记录下这个子串的长度；
在枚举结束后，我们找到的最长的子串的长度即为答案。
代码实现
此题解法的核心是：向右扩张时，无重复则记录，有重复则中止，这样能获取到非重复子串的右边界。
当获取到右边界后， 这个窗口无法再进行扩张了，此时左边界需要右移，右移后又需要把边界之外的元素给移除，因此有了 windows.remove(s.charAt(index - 1)); 这一操作
每次获取到最大非重复字串时记录最大长度。 最终便得到了整个字符串的非重复子串的最大长度。
class Solution {
public int lengthOfLongestSubstring(String s) {
int maxLen = 0;
int right = 0;
// 滑动窗口，记录不重复的字串
Set<Character> windows = new HashSet<Character>();
// 窗口的左边界
for (int index = 0; index < s.length(); index++) {
if (index != 0) {
// 再次进入到循环， 说明已经遇到重复的了。此时将记录的上个循环的最左侧字符移除掉
windows.remove(s.charAt(index - 1));
}
for (; right < s.length() && !windows.contains(s.charAt(right)); right++) {
// 窗口右侧，当右侧向右扩张的过程中没遇到重复的，则记录进hash表
// 遇到重复的则循环结束
windows.add(s.charAt(right));
}
// 计算窗口最长的长度
maxLen = Math.max(right - index, maxLen);
}
return maxLen;
}
}
看了另一个滑动窗口的解法。 确保list 中一直是非重复子串，因此只需要记录数组的最大长度即可。
class Solution {
public int lengthOfLongestSubstring(String s) {
int maxLen = 0;
// 使用数组， 保证窗口有序
List<Character> windows = new ArrayList<>();
for (int index = 0; index < s.length(); index++) {
// 使用while循环，移除窗口中已出现的字符前的内容， 确保窗口中不出现重复字符
while (windows.contains(s.charAt(index))) {
windows.remove(0);
}
windows.add(s.charAt(index));
maxLen = Math.max(maxLen, windows.size());
}
return maxLen;
}
}
219. 存在重复元素 II
这题是一道简单题，在做过题三之后，带着滑动窗口的思维来做这道题还是比较简单的。
我们先来看下题目：
给你一个整数数组 nums 和一个整数 k ，判断数组中是否存在两个 不同的索引 i 和 j ，满足 nums[i] == nums[j] 且 abs(i - j) <= k 。如果存在，返回 true ；否则，返回 false 。
示例 1：
输入：nums = [1,2,3,1], k = 3
输出：true
示例 2：输入：nums = [1,0,1,1], k = 1
输出：true
示例 3：输入：nums = [1,2,3,1,2,3], k = 2
输出：false
其中， 针对下标的限定条件abs(i - j) <= k， 我们可以理解为滑动窗口的窗口大小为k， 超出k之后滑动窗口就不能再进行扩张了，需要丢弃最早的那个元素了。因此向右扩张，无法扩张时丢弃早期元素这一思想，可以得到以下解法。
class Solution {
public boolean containsNearbyDuplicate(int[] nums, int k) {
Set<Integer> set = new HashSet<>();
int right = 0;
for (int index = 0; index < nums.length; index++) {
if(index > 0){
// 扩张到了极限之后，每次移除最早进入窗口的元素
set.remove(nums[index-1]);
}
// 右侧边界未出界，且窗口的大小（right - index） 在限定值之内， 判断是否符合nums[i] == nums[j]的元素，同时将右侧的元素写入窗口队列。
while (right < nums.length && right - index <= k) {
if (set.contains(nums[right])) {
return true;
}
set.add(nums[right]);
right++;
}
}
return false;
}
}
209. 长度最小的子数组
给定一个含有 n 个正整数的数组和一个正整数 target 。
找出该数组中满足其总和大于等于 target 的长度最小的 子数组 [numsl, numsl+1, ..., numsr-1, numsr] ，并返回其长度。如果不存在符合条件的子数组，返回 0 。
在拿到这题之后，我还在想不连续的情况下如何取用滑动窗口去解决，失败好几次后我发现，有个细节被我忽略了。子数组 是数组中连续的 非空 元素序列。
于是：
class Solution {
public int minSubArrayLen(int target, int[] nums) {
int sum = 0;
int min = Integer.MAX_VALUE;
int start = 0;
for (int i = 0; i < nums.length; i++) {
while (sum < target && start < nums.length) {
sum += nums[start++];
}
if (sum >= target) {
sum -= nums[i];
min = Math.min(min, start - i);
}
}
return min == Integer.MAX_VALUE ? 0 : min;
}
}