跳到主要内容

无重复字符的最长子串

题目描述​

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

示例​

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

提示：

  • 0 <= s.length <= 5 * 10^4
  • s 由英文字母、数字、符号和空格组成

解题思路​

滑动窗口

使用两个指针表示窗口的左右边界，右指针不断向右移动，左指针在必要时向右移动以保持窗口内无重复字符。

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

C++ 解法​

#include <algorithm>
#include <string>
#include <unordered_map>

class Solution {
public:
    int lengthOfLongestSubstring(std::string s)
    {
        int n = s.length();
        int maxLength = 0;

        std::unordered_map<char, int> charMap;

        // 滑动窗口左边界
        int left = 0;

        for (int right = 0; right < n; right++) {
            char currentChar = s[right];
            if (charMap.find(currentChar) != charMap.end()) {
                // 如果当前字符在map中存在，则更新左边界
                left = std::max(left, charMap[currentChar] + 1);
            }

            // 更新字符位置
            charMap[currentChar] = right;
            // 更新最大长度
            maxLength = std::max(maxLength, right - left + 1);
        }
        return maxLength;
    }
};

LeetCode链接： 3. 无重复字符的最长子串