滑动窗口和红蓝染色

一、LeetCode 3：无重复字符的最长子串

1. 前提条件
   题目给你一个字符串：
   char* s
   要求你返回：
   不含重复字符的最长子串长度
   注意是：
   子串 substring：必须连续
   子序列 subsequence：可以不连续
   例如：
   s = "abcabcbb"
   答案是："abc"
   长度 = 3
   也可以是 "bca" 或 "cab"，只要长度是 3 即可。

2. 核心概念：滑动窗口
   滑动窗口适合处理这种问题：

在一段连续区间里，维护某种条件。

第 3 题里的条件是：窗口内不能有重复字符。

我们用两个指针：

int left = 0;
int right = 0;

表示当前窗口：[left, right]

也就是当前正在检查的一段连续子串。

例如：

s = "abcabcbb"

left = 0
right = 2
窗口 = "abc"

这个窗口没有重复字符，所以可以更新答案。

3. 滑动窗口的基本思想

滑动窗口一般分两步：（最重要的一点和计网的GBN回退N步那里用到的方法一样）

1. right 向右扩张，把新字符加入窗口。
2. 如果窗口不合法，就移动 left 缩小窗口，直到重新合法。

第 3 题中：合法条件：窗口内没有重复字符。

所以：

如果 right 加进来的字符重复了，就不断 left++，把左边字符移出窗口。
4. 固定模板
int left = 0;
int ans = 0;

for (int right = 0; right < n; right++) {
// 1. 把 s[right] 加入窗口

while (窗口不合法) {
    // 2. 移出 s[left]
    left++;
}

// 3. 此时窗口合法，更新答案
ans = max(ans, right - left + 1);

}

第 3 题中，窗口是否合法要看字符是否重复，所以可以用一个数组记录字符出现次数：

int count[256] = {0};
5. C 语言代码模板

int lengthOfLongestSubstring(char* s) {
int count[256] = {0};

int left = 0;
int ans = 0;

for (int right = 0; s[right] != '\0'; right++) {
    unsigned char c = s[right];
    count[c]++;

//这里用c来表示这个字符，之后根据ASCII对应在数组里面的位置，不重复就加位置对应的值成1，然后right增加
while (count[c] > 1) {
unsigned char d = s[left];
count[d]--;
left++;
}
//这里是发现重复了，所以left取到之后把次数清0，然后左窗口往右移动
int len = right - left + 1;
if (len > ans) {
ans = len;
}
}

return ans;

}
6. 代码怎么跑？

以：

s = "abcabcbb"

为例。

一开始：

left = 0
right = 0
窗口 = "a"
ans = 1

继续扩张：

窗口 = "ab"
ans = 2

继续扩张：

窗口 = "abc"
ans = 3

再加入下一个 'a'：

窗口 = "abca"

现在 'a' 重复了，不合法。

于是移动 left，把左边的 'a' 移出去：

窗口 = "bca"

又合法了。

所以这题本质是：

right 负责扩大窗口；
left 负责在重复时缩小窗口；
每次窗口合法后更新最大长度。
7. 为什么 while (count[c] > 1)？

因为我们每次新加入的是：

s[right]

只有这个新字符可能导致重复。

所以只需要判断：

count[s[right]] > 1

如果它重复了，就移动 left，直到这个字符不重复为止。

例如：

s = "abba"

当窗口变成：

"abb"

第二个 'b' 进来后，b 重复了。

移动 left：

去掉 'a' 后，窗口 = "bb"

还是重复。

继续移动：

去掉第一个 'b' 后，窗口 = "b"

这时合法。

所以这里必须是 while，不能只用 if。

8. 易错点
   易错点 1：把子串和子序列搞混
   子串：必须连续
   子序列：可以不连续

第 3 题要的是连续子串。

易错点 2：窗口不合法时只移动一次 left

错误想法：

if (count[c] > 1) {
left++;
}

不一定够。

比如：

s = "abba"

遇到第二个 'b' 时，只移动一次 left 去掉 'a'，窗口还是 "bb"，仍然重复。

所以要写：

while (count[c] > 1)
易错点 3：更新答案的位置

应该在窗口合法之后更新：

int len = right - left + 1;
if (len > ans) {
ans = len;
}

不能在窗口还重复时更新。

易错点 4：C 语言字符串可以用 '\0' 判断结束

因为字符串有结束标志：

s[right] != '\0'

普通数组不行，普通数组必须靠 numsSize。

9. 复杂度
   时间复杂度：O(n)
   空间复杂度：O(1)

为什么时间是 O(n)？

因为：

right 每个字符只走一次；
left 每个字符最多也只走一次。

虽然里面有 while，但整体不是 O(n^2)。

10. 题型总结

第 3 题属于：

滑动窗口 / 同向双指针

规律：

窗口合法：right 继续扩张，更新答案；
窗口不合法：left 收缩窗口，直到合法。

一句话：

第 3 题的滑动窗口，本质是维护一个“不含重复字符”的连续区间。
二、LeetCode 34：二分查找 / 红蓝染色法

1. 前提条件

题目给你：

int* nums
int numsSize
int target

并且数组满足：

nums 是非递减排序数组

也就是：

允许重复元素的升序数组。

要求返回：

target 第一次出现的位置和最后一次出现的位置。

例如：

nums = [5,7,7,8,8,10]
target = 8

答案：

[3,4]

如果不存在：

[-1,-1]

题目还要求：

时间复杂度必须是 O(log n)

所以不能从头遍历。

2. 核心概念：找边界

这题不是普通二分找一个 target 就完事。

因为数组里可能有多个 target：

[5, 7, 7, 8, 8, 10]
^ ^
左边界 右边界

所以要找两个位置：

第一个 >= target 的位置
第一个 > target 的位置

然后：

左边界 = 第一个 >= target 的位置
右边界 = 第一个 > target 的位置 - 1

例如：

nums = [5,7,7,8,8,10]
target = 8

第一个 >= 8 的位置是：

index = 3

第一个 > 8 的位置是：

index = 5

所以右边界是：

5 - 1 = 4

答案就是：

[3,4]
三、红蓝染色法

1. 红蓝染色法是什么？

红蓝染色法就是把数组位置分成两类：

蓝色：不满足条件
红色：满足条件

二分的目标是：

找到第一个红色位置。

这个模板非常适合找：

第一个 >= target
第一个 > target
第一个满足某条件的位置
2. 找第一个 >= target

条件是：

nums[i] >= target

对于排序数组：

nums = [5,7,7,8,8,10]
target = 8

染色：

索引： 0 1 2 3 4 5
值： 5 7 7 8 8 10
颜色： 蓝 蓝 蓝 红 红 红

因为：

5,7,7 都 < 8，不满足 nums[i] >= 8，所以是蓝色；
8,8,10 都 >= 8，满足条件，所以是红色。

我们要找：

第一个红色

也就是 index = 3。

3. 红蓝染色固定模板

这个模板建议你背下来：

int lowerBoundGE(int* nums, int numsSize, int target) {
int blue = -1;
int red = numsSize;

while (blue + 1 < red) {
    int mid = blue + (red - blue) / 2;

    if (nums[mid] >= target) {
        red = mid;
    } else {
        blue = mid;
    }
}

return red;

}

这里：

blue = -1 表示最左边虚拟蓝色位置
red = numsSize 表示最右边虚拟红色位置

也就是：

[-1, numsSize]

一开始我们假设：

-1 一定是蓝色
numsSize 一定是红色

这两个是虚拟边界，不是真实数组元素。

循环结束时：

blue + 1 == red

说明蓝色和红色挨在一起了。

此时：

red 就是第一个红色位置。
4. 为什么 nums[mid] >= target 时 red = mid？

因为我们现在要找的是：

第一个满足 nums[i] >= target 的位置。

如果：

nums[mid] >= target

说明 mid 已经是红色。

但是它不一定是第一个红色，左边可能还有红色。

所以要往左收缩：

red = mid;

如果：

nums[mid] < target

说明 mid 是蓝色。

那么第一个红色一定在右边，所以：

blue = mid;
5. 找第一个 > target

同理，条件换成：

nums[i] > target

代码：

int lowerBoundGT(int* nums, int numsSize, int target) {
int blue = -1;
int red = numsSize;

while (blue + 1 < red) {
    int mid = blue + (red - blue) / 2;

    if (nums[mid] > target) {
        red = mid;
    } else {
        blue = mid;
    }
}

return red;

}

例如：

nums = [5,7,7,8,8,10]
target = 8

按 nums[i] > 8 染色：

索引： 0 1 2 3 4 5
值： 5 7 7 8 8 10
颜色： 蓝 蓝 蓝 蓝 蓝 红

第一个红色位置是：

index = 5

所以：

最后一个 8 的位置 = 5 - 1 = 4
四、第 34 题完整 C 代码
#include <stdlib.h>

int lowerBoundGE(int* nums, int numsSize, int target) {
int blue = -1;
int red = numsSize;

while (blue + 1 < red) {
    int mid = blue + (red - blue) / 2;

    if (nums[mid] >= target) {
        red = mid;
    } else {
        blue = mid;
    }
}

return red;

}

int lowerBoundGT(int* nums, int numsSize, int target) {
int blue = -1;
int red = numsSize;

while (blue + 1 < red) {
    int mid = blue + (red - blue) / 2;

    if (nums[mid] > target) {
        red = mid;
    } else {
        blue = mid;
    }
}

return red;

}

int* searchRange(int* nums, int numsSize, int target, int* returnSize) {
int* ans = malloc(2 * sizeof(int));
*returnSize = 2;

int left = lowerBoundGE(nums, numsSize, target);

if (left == numsSize || nums[left] != target) {
    ans[0] = -1;
    ans[1] = -1;
    return ans;
}

int right = lowerBoundGT(nums, numsSize, target) - 1;

ans[0] = left;
ans[1] = right;

return ans;

}
5. 为什么不用 target + 1？

有些写法会这样：

right = lowerBoundGE(nums, numsSize, target + 1) - 1;

在普通整数范围内可以理解。

但是更稳的写法是：

right = lowerBoundGT(nums, numsSize, target) - 1;

因为如果 target 已经是很大的整数，target + 1 可能溢出。

所以推荐记：

左边界：第一个 >= target
右边界：第一个 > target 的位置 - 1
6. 第 34 题易错点
易错点 1：普通二分只能找到一个 target

普通二分可能找到中间那个：

[5,7,7,8,8,10]
或者

但题目要的是：

第一个 target 和最后一个 target。

所以要找边界。

易错点 2：left == numsSize 要先判断

如果：

left == numsSize

说明数组里没有任何元素 >= target。

此时不能访问：

nums[left]

因为越界了。

所以必须写：

if (left == numsSize || nums[left] != target)

注意 C 语言的短路特性：

left == numsSize 为真时，后面的 nums[left] 不会再判断。
易错点 3：二分循环条件

红蓝染色法固定写：

while (blue + 1 < red)

结束时：

blue 和 red 相邻
red 是第一个红色

不要和其他二分模板混在一起。

易错点 4：mid 推荐这样写
int mid = blue + (red - blue) / 2;

不推荐：

int mid = (blue + red) / 2;

因为 blue + red 理论上可能溢出。

7. 第 34 题复杂度
   时间复杂度：O(log n)
   空间复杂度：O(1)

虽然调用了两次二分，但还是：

O(log n) + O(log n) = O(log n)
8. 第 34 题题型总结
第 34 题 = 二分找边界。

左边界：
找第一个 nums[i] >= target 的位置。

右边界：
找第一个 nums[i] > target 的位置，再减 1。

红蓝染色法：
蓝色 = 不满足条件
红色 = 满足条件
目标 = 找第一个红色。

最核心一句：

找范围不要普通二分找 target，要二分找左右边界。