LeetCode 算法：无重复字符的最长子串c++

原题链接🔗：无重复字符的最长子串
难度：中等⭐️⭐️

题目

给定一个字符串 s ，请你找出其中不含有重复字符的最长子串的长度。

示例 1:
输入: s = “abcabcbb”
输出: 3
解释: 因为无重复字符的最长子串是 “abc”，所以其长度为 3。

示例 2:
输入: s = “bbbbb”
输出: 1
解释: 因为无重复字符的最长子串是 “b”，所以其长度为 1。

示例 3:
输入: s = “pwwkew”
输出: 3
解释: 因为无重复字符的最长子串是 “wke”，所以其长度为 3。
请注意，你的答案必须是 子串 的长度，“pwke” 是一个子序列，不是子串。

提示：
0 <= s.length <= 5 * 10⁴
s 由英文字母、数字、符号和空格组成

题解

滑动窗口法

1. 题解：使用滑动窗口的方法，通过两个指针表示子串的开始和结束位置，利用哈希表来记录字符的出现情况。

2. 复杂度：时间复杂度O(N)，空间复杂度O(N)。

3. 代码过程：

• 初始化 start 和 end 指针，分别指向子串的开始和结束。
• 初始化一个哈希表 charIndexMap 来存储字符及其索引。
• 初始化maxLength 变量来记录最长子串的长度。
• 遍历字符串 s：
  • 对于每个字符 s[end]：
    • 如果字符已在 charIndexMap中，并且索引不小于 start：
      • 更新 start 为 charIndexMap[s[end]] + 1。
    • 更新charIndexMap[s[end]] 为当前的 end 索引。
    • 更新 maxLength 为 end - start + 1。
• 返回maxLength

4. c++ demo：

#include <iostream>
#include <string>
#include <unordered_map>
using namespace std;

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        unordered_map<char, int> charIndexMap; // 存储字符及其索引
        int maxLength = 0;
        int start = 0; // 窗口的起始位置

        for (int end = 0; end < s.size(); ++end) {
            char currentChar = s[end];
            // 如果字符已存在于哈希表中，且其索引不小于窗口起始位置，则移动窗口起始位置
            if (charIndexMap.find(currentChar) != charIndexMap.end() && charIndexMap[currentChar] >= start) {
                start = charIndexMap[currentChar] + 1;
            }

            // 更新字符的索引
            charIndexMap[currentChar] = end;
            // 更新最长子串的长度
            maxLength = max(maxLength, end - start + 1);
        }

        return maxLength;
    }
};

int main() {
    Solution solution;
    string input = "abcabcbb";
    cout << "The length of the longest substring without repeating characters is: "
        << solution.lengthOfLongestSubstring(input) << endl;
    return 0;
}

• 输出结果：

The length of the longest substring without repeating characters is: 3

滑动窗口法

滑动窗口是一种非常有用的算法思想，特别是在处理与字符串、数组或数据流中连续子串或子数组有关的问题时。它的核心思想是通过维护一个可以滑动的窗口来遍历整个数据结构，窗口内的数据满足特定条件。

基本概念

• 窗口：指的是数据结构（如字符串或数组）中连续的一部分。
• 滑动窗口：随着遍历的进行，窗口可以向右滑动，即窗口的起始位置和结束位置可以动态变化。

应用场景

滑动窗口常用于解决如下问题：

1. 最长不重复子串/子数组：找到不包含重复元素的最长连续子串或子数组。
2. 频率限制：如 LRU 缓存机制，需要维护一个固定大小的窗口，以确定哪些元素应该被移除。
3. 滑动窗口最大值/最小值：在给定的滑动窗口内找到最大值或最小值。
4. 区间和/乘积问题：在滑动窗口内计算和或乘积。

算法步骤

1. 初始化：设置窗口的起始和结束位置，通常起始位置 start 和结束位置 end 都初始化为 0。
2. 扩展窗口：将 end 指针向右移动，扩展窗口，直到窗口不再满足特定条件（如包含重复字符）。
3. 收缩窗口：移动 start 指针，使窗口收缩，直到再次满足条件。
4. 更新答案：在每次窗口调整后，根据问题需求更新答案（如最长长度、最大值等）。
5. 重复：重复扩展和收缩窗口的过程，直到结束位置 end 到达数据结构的末尾。

示例：

最长不重复子串 以 “无重复字符的最长子串” 问题为例：

1. 初始化两个指针 start 和 end，指向字符串的起始位置。
2. 使用哈希表记录窗口内字符的索引。
3. 扩展窗口：将 end 向右移动，直到遇到重复字符。
4. 收缩窗口：更新 start 为重复字符的下一个索引，排除重复字符。
5. 在每次窗口调整后，计算窗口的长度，更新最长子串长度。

总结

滑动窗口是一种高效解决问题的方法，通过动态调整窗口大小来找到满足条件的子串或子数组。它在处理连续性问题时特别有用，并且可以很容易地适应不同的问题需求

。