Leetcode 无重复字符的最长子串
算法思想：
- 滑动窗口：通过
start和end来维护一个滑动窗口，start指向当前窗口的起点，end是当前窗口的末尾。滑动窗口中的字符都是无重复的。 - 哈希表
charIndexMap：用于存储每个字符及其最近一次出现的位置。 - 更新起始位置：如果当前字符已经在滑动窗口中出现过（即它在
charIndexMap中），则将窗口的起始位置start更新为该字符上次出现位置的下一个位置。 - 更新最长长度：每次移动
end时，计算当前窗口的长度，并更新最大长度maxLength。 - 时间复杂度：O(n)，每个字符最多被访问两次（一次通过
end，一次通过start）。
一个字符如果已经存在于哈希表 charIndexMap 中作为 key，那么它必然已经在滑动窗口中出现过（或者至少在当前遍历之前出现过）
哈希表charIndexMap为什么只存储每个字符最近一次出现的位置？
哈希表 charIndexMap 只存储每个字符最近一次出现的位置是关键的，因为它帮助我们高效地处理字符重复问题。让我们深入分析这个策略的核心原因：
1. 滑动窗口的高效性：
在解决这个问题时，我们使用了滑动窗口的思路，维护窗口中无重复字符的子串。如果当前字符已经出现在窗口中，我们需要将窗口的起始位置 start 移动到这个字符上一次出现的位置之后。
例如，假设我们处理字符串 "abcabcbb"，当我们扫描到第二个 'a' 时，我们需要知道第一个 'a' 在字符串中的位置，从而更新 start 位置。如果我们总是记录字符最近一次的位置，就可以通过直接访问 charIndexMap 中的值，快速找到这个字符上次出现的位置，并更新窗口的起始位置。
2. 无重复字符：
为了确保滑动窗口中的子串没有重复字符，我们只关心当前字符的最近一次出现位置。因为滑动窗口始终向右移动，每个字符可能会出现在滑动窗口内一次或多次，但我们只关心最近一次出现时的位置，这样才能根据它来决定是否需要缩小窗口大小。
例子：
考虑字符串 "abca"，当我们扫描到第二个 'a' 时，窗口是从 start = 0 到 end = 3。为了保持子串中的字符不重复，我们必须将 start 移动到第一次 'a' 之后，也就是位置 1。所以我们更新 start = charIndexMap['a'] + 1。如果哈希表里记录的不是最近一次出现的 'a'，我们就无法正确更新 start 位置，滑动窗口会无法维持无重复的子串。
3. 避免重复计算：
通过记录最近一次出现的位置，我们可以在常数时间内查找每个字符是否在滑动窗口中出现过。如果哈希表里保存的是某个字符的所有出现位置，那么我们需要逐个遍历所有出现的位置，这样会降低算法效率，导致无法在 O(n) 时间内完成。
例如，假设我们使用一个数据结构记录字符所有出现的位置，对于每个新的字符，我们需要检查这个数据结构的所有位置来决定窗口的起点，这样时间复杂度会增加到 O(n^2)，大大降低了算法的效率。
4. 滑动窗口的合法性更新：
当我们遇到重复字符时，我们只需要关心这个字符最近一次出现在滑动窗口中的位置，并且根据它来调整窗口的起点。这种做法使得我们能够在一次扫描中动态维护窗口，且保证窗口内的字符始终无重复。
举个例子：
对于字符串 "tmmzuxt"，当我们扫描到第二个 'm' 时，窗口变为 "tm"，此时遇到重复字符 'm'，我们需要更新 start 到第一个 'm' 之后的位置。我们只需要存储每个字符最近出现的索引来做到这一点。
总结：
哈希表 charIndexMap 只存储每个字符最近一次出现的位置，是为了在滑动窗口中快速查找字符的最近出现情况，从而在 O(1) 的时间内决定是否需要更新窗口的起点。这样可以确保算法的时间复杂度为 O(n)，在处理大规模输入时仍能高效运行。
#include <iostream>
#include <unordered_map>
#include <string>
using namespace std;int lengthOfLongestSubstring(string s) {unordered_map<char, int> charIndexMap; // 存储字符和其索引int maxLength = 0; // 无重复字符子串的最大长度int start = 0; // 滑动窗口的起始位置for (int end = 0; end < s.length(); ++end) {char currentChar = s[end];// 如果当前字符已经在滑动窗口中，更新起始位置到其下一个位置if (charIndexMap.find(currentChar) != charIndexMap.end()) {start = max(start, charIndexMap[currentChar] + 1);}// 更新当前字符的索引charIndexMap[currentChar] = end;// 更新最大长度maxLength = max(maxLength, end - start + 1);}return maxLength;
}int main() {string s;cout << "请输入一个字符串: ";cin >> s;int result = lengthOfLongestSubstring(s);cout << "无重复字符的最长子串长度为: " << result << endl;return 0;
}
这一行代码, 为什么需要和start进行max比较而不是直接使用charIndexMap[currentChar] + 1进行更新？
start = max(start, charIndexMap[currentChar] + 1);
这是一个很好的问题！代码中这一行：
在更新滑动窗口的起点 start 时，之所以需要和 start 进行 max 比较，而不是直接使用 charIndexMap[currentChar] + 1，原因在于当前的 start 可能已经在该字符后面了。我们需要确保 start 只会向前移动，而不会回退。下面详细解释这个原因。
详细原因：
1. 字符可能之前已经出现在窗口外：
当我们遇到一个已经在哈希表中存在的字符时，它的上一次出现位置可能已经在当前窗口外，即在 start 之前。例如，如果 start 已经向前移动到了超过该字符上一次出现的位置，我们就不应该让 start 回退到它之前的地方。
举例：
假设我们处理字符串 "abcdaefg"。
- 当
end扫描到第一个'a'时，窗口为"a"。 - 扫描到
"abcda"，第二个'a'重复，charIndexMap['a'] = 0，所以我们应该更新start为charIndexMap['a'] + 1 = 0 + 1 = 1，此时窗口变成"bcda"。 - 接着扫描到
'e'和'f'，没有问题，窗口为"bcdae"和"bcdaef"。 - 最后扫描到
'g'，窗口为"bcdaefg"。
如果你在遇到重复字符 'a' 时直接把 start 更新为 charIndexMap['a'] + 1 = 1，并不需要多此一举，因为 start 本身已经是 1 或更大了。
2. 防止 start 回退：
如果不使用 max 比较，而是直接将 start 更新为 charIndexMap[currentChar] + 1，可能会导致窗口的起点 start 回退，破坏滑动窗口的正确性。
举个详细的例子：
考虑字符串 "abba"，滑动窗口的过程如下：
end = 0，start = 0，窗口为"a"，无重复。end = 1，start = 0，窗口为"ab"，无重复。end = 2，start = 0，遇到重复字符'b'，charIndexMap['b'] = 1，所以start = charIndexMap['b'] + 1 = 2，窗口变为"b"。- 接着
end = 3，start = 2，遇到重复字符'a'，此时如果直接将start更新为charIndexMap['a'] + 1 = 0 + 1 = 1，则会导致start回退到 1，实际上窗口已经过了位置 1。因此，更新start时需要比较max(start, charIndexMap[currentChar] + 1)，保持start不会回退。
通过 max(start, charIndexMap[currentChar] + 1)，我们确保 start 只会向右移动，保证滑动窗口合法，并且避免了让 start 回退到一个可能包含重复字符的位置。
3. 总结：
start = max(start, charIndexMap[currentChar] + 1); 的目的是为了防止滑动窗口的起点回退。当我们遇到重复字符时，如果该字符的上次出现位置已经在 start 之前（即窗口外），我们不应该让 start 回退。因此我们需要将 start 与 charIndexMap[currentChar] + 1 进行比较，确保 start 总是向前移动，保持滑动窗口的无重复性。
这个 max 操作确保滑动窗口的正确性，并保证算法的时间复杂度为 O(n)。
关于这一部分代码片段，为什么先更新start，后更新end？是否可以先更新end，后更新start？
// 如果当前字符已经在滑动窗口中，更新起始位置到其下一个位置if (charIndexMap.find(currentChar) != charIndexMap.end()) {start = max(start, charIndexMap[currentChar] + 1);}// 更新当前字符的索引charIndexMap[currentChar] = end;
在这段代码中，更新 start 和更新 end 的顺序是非常重要的。让我们分析为什么必须先更新 start，再更新 end，以及如果反过来会导致什么问题。
代码逻辑回顾：
// 如果当前字符已经在滑动窗口中，更新起始位置到其下一个位置
if (charIndexMap.find(currentChar) != charIndexMap.end()) {start = max(start, charIndexMap[currentChar] + 1);
}// 更新当前字符的索引
charIndexMap[currentChar] = end;
为什么要先更新 start 再更新 end？
-
滑动窗口需要维持无重复字符的状态：
当我们发现当前字符currentChar已经在charIndexMap中（说明之前已经出现过），为了确保滑动窗口中的子串不包含重复字符，必须先更新窗口的起点start，使窗口“跳过”重复的字符。- 如果我们先更新
end，然后再处理start的话，charIndexMap[currentChar]将会被更新为当前的end，那么它就代表了字符currentChar的最新位置，导致无法获取该字符之前出现的位置。这会破坏我们本该依据字符之前出现位置来调整start的逻辑，最终导致窗口中可能会保留重复字符。
举个例子：
- 假设字符串为
"abcba"，我们正在处理字符'b'。 charIndexMap['b']的值本来是1（第一次出现位置）。- 如果我们先更新
end，那么charIndexMap['b']就变成了当前的4（第二次出现的位置），这样后面判断重复字符的时候，我们就不能正确获取b的第一次出现位置（索引1），从而不能正确更新start。
- 如果我们先更新
-
start是根据字符的旧位置来更新的：
只有在更新start之前，字符currentChar在charIndexMap中的值才是它上一次出现的索引。如果我们提前更新charIndexMap[currentChar]，就会丢失这个关键信息。因此，必须先利用charIndexMap[currentChar]获取字符的旧位置，然后更新start，之后再将charIndexMap[currentChar]更新为end（最新的索引）。
如果先更新 end，会出现什么问题？
假设我们反过来写成：
// 先更新当前字符的索引
charIndexMap[currentChar] = end;// 如果当前字符已经在滑动窗口中，更新起始位置到其下一个位置
if (charIndexMap.find(currentChar) != charIndexMap.end()) {start = max(start, charIndexMap[currentChar] + 1);
}
问题：如果你先更新 charIndexMap[currentChar] = end，那么 charIndexMap[currentChar] 将会被更新为当前字符的最新位置，导致后面的 start = max(start, charIndexMap[currentChar] + 1) 其实是在基于当前字符的最新位置来更新 start。这样你会丢失该字符上次出现时的索引信息，滑动窗口中的字符不会被正确地排除掉，可能导致窗口中保留了重复字符。
举例：
假设处理字符串 "abcb"，当 end = 3 时，遇到重复的 'b'：
- 如果我们先更新
charIndexMap['b'] = 3，那么charIndexMap['b']现在指向的是最新的3，而不是上一次'b'出现的位置1。 - 当你之后再试图更新
start时，charIndexMap['b'] + 1 = 3 + 1 = 4，导致start被更新到超出当前窗口范围的地方，错误地跳过了整个窗口，这显然是错误的。
总结：
- 先更新
start是为了确保我们使用的是字符上次出现的位置，从而调整滑动窗口，保持无重复字符的子串。 - 再更新
end是为了记录当前字符的新位置，为后续的判断做好准备。 - 如果反过来操作，先更新
end会导致我们丢失字符上次出现的位置，从而不能正确更新start，最终滑动窗口无法保证无重复字符。
因此，先更新 start，后更新 end 是必要的顺序，保证了逻辑正确性。