力扣 leetcode 3. 无重复字符的最长子串()

题目描述

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

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

示例

示例1:

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

示例2:

输入: s = "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b",所以其长度为 1。

示例3:

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

解体思路

最简单的思路是遍历整个字符串,假设当前遍历的下标为,是无重复子串的起始下标。如果,则将置为。具体代码如下:

i
cur_index
s[i]==s[j]
cur_index
cur_index = j+1
class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        // s的长度小于2时,直接返回最终结果
        if(s.size() < 2){
            return s.size();
        }
        // 最小的无重复子串的长度为1
        int max_len = 1;
        // 记录当前无重复字符子串的起始位置
        int cur_index = 0;
        for(int i = 1; i < s.size(); i++){
            for(int j = cur_index; j < i; j++){
                // 判断是否出现重复字符
                if(s[i] == s[j]){
                    // 新的无重复字符子串下标从j+1开始
                    cur_index = j + 1;
                    break;
                }
                // 判断当前子串长度是否超出最大值
                max_len = max_len > (j - cur_index + 2) ? max_len : (j - cur_index + 2);
            }
        }
        return max_len;
    }
};
————————

题目描述

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

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

示例

示例1:

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

示例2:

输入: s = "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b",所以其长度为 1。

示例3:

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

解体思路

最简单的思路是遍历整个字符串,假设当前遍历的下标为,是无重复子串的起始下标。如果,则将置为。具体代码如下:

i
cur_index
s[i]==s[j]
cur_index
cur_index = j+1
class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        // s的长度小于2时,直接返回最终结果
        if(s.size() < 2){
            return s.size();
        }
        // 最小的无重复子串的长度为1
        int max_len = 1;
        // 记录当前无重复字符子串的起始位置
        int cur_index = 0;
        for(int i = 1; i < s.size(); i++){
            for(int j = cur_index; j < i; j++){
                // 判断是否出现重复字符
                if(s[i] == s[j]){
                    // 新的无重复字符子串下标从j+1开始
                    cur_index = j + 1;
                    break;
                }
                // 判断当前子串长度是否超出最大值
                max_len = max_len > (j - cur_index + 2) ? max_len : (j - cur_index + 2);
            }
        }
        return max_len;
    }
};