溧阳城乡建设局网站,谷城网站定制,千万别在百度上搜别人的名字,深圳南头高端网站建设算法思想#xff1a;
滑动窗口#xff1a;通过 start 和 end 来维护一个滑动窗口#xff0c;start 指向当前窗口的起点#xff0c;end 是当前窗口的末尾。滑动窗口中的字符都是无重复的。哈希表 charIndexMap#xff1a;用于存储每个字符及其最近一次出现的位置。更新起始…算法思想
滑动窗口通过 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_mapchar, 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 0start 0窗口为 a无重复。end 1start 0窗口为 ab无重复。end 2start 0遇到重复字符 bcharIndexMap[b] 1所以 start charIndexMap[b] 1 2窗口变为 b。接着 end 3start 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 是必要的顺序保证了逻辑正确性。
