剑指48：最长不含重复字符的子字符串

传送门

nowcoder
leetcode

题目描述

请从字符串中找出一个最长的不包含重复字符的子字符串，计算该最长子字符串的长度。

C++ 代码 - nowcoder

/*
    哈希表 + 双指针

    时间复杂度：O(n)
*/
class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        int length = s.size();
        if (length <= 1) return length;

        unordered_set<char> set;
        int res = -1, right = 0;
        for (int left = 0; left < length; left ++) {
            while (right < length && !set.count(s[right])) {
                set.insert(s[right]);
                right ++;
            }
            res = max(res, right - left);
            set.erase(s[left]);
            if (right >= length) break;
        }
        
        return res;
    }
};

/*
	滑动窗口
	
	时间复杂度：O(n)
*/
class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        unordered_map<char, int> window;

        int left = 0, right = 0;
        int res = 0; // 记录结果
        while (right < s.size()) {
            char c = s[right];
            right ++;
            // 窗口内的数据进行更新
            window[c] ++;
            // 判断左侧窗口是否需要收缩
            while (window[c] > 1) {
                char t = s[left];
                left ++;
                // 窗口内的数据进行更新
                window[t] --;
            }
            // 更新答案
            res = max(res, right - left);
        }
        return res;
    }
};

C++ 代码 - leetcode

/*
	滑动窗口
	
	时间复杂度：O(n)
*/
class Solution {
    public:
    int lengthOfLongestSubstring(string s) {
        unordered_map<char, int> window;

        int left = 0, right = 0;
        int res = 0; // 记录结果
        while (right < s.size()) {
            char c = s[right];
            right ++;
            // 窗口内的数据进行更新
            window[c] ++;
            // 判断左侧窗口是否需要收缩
            while (window[c] > 1) {
                char t = s[left];
                left ++;
                // 窗口内的数据进行更新
                window[t] --;
            }
            // 更新答案
            res = max(res, right - left);
        }
        return res;
    }
};