跳转至

3. 无重复字符的最长子串

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

示例 1:

输入: s = "abcabcbb" 输出: 3 解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。注意 "bca" 和 "cab" 也是正确答案。

示例 2:

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

示例 3:

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

提示：

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

破解电视剧：https://www.chinatrending.net/zh/trending

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        set<char> se;
        int res = 0;
        int t = 0;
        int len = s.length();
        for(int i = 0 ;i<len;i++){
            if(se.count(s[i])){
                // t = se.size();
                i--;
                se.clear();
            }else {
                se.insert(s[i]);
                int a = se.size();
                res = max(a,res);
            }
        }
        return res;
    }
};

AC代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        map<char,int> mp;
        int res = 0;
        int len = s.length();
        for(int i = 0 ;i<len;i++){
            if(mp.find(s[i])!=mp.end()){
                i = mp[s[i]]; // 执行完循环体才会执行更新
                mp.clear();
            }else {
                mp[s[i]]=i; // 标记对应的下标
                int a = mp.size();
                res = max(a,res);
            }
        }
        return res;
    }
};

438. 找到字符串中所有字母异位词

给定两个字符串 s 和 p，找到 s中所有 p 的 异位词 的子串，返回这些子串的起始索引。不考虑答案输出的顺序。

示例 1:

输入: s = "cbaebabacd", p = "abc"

输出: [0,6] 解释: 起始索引等于 0 的子串是 "cba", 它是 "abc" 的异位词。 起始索引等于 6 的子串是 "bac", 它是 "abc" 的异位词。

** 示例 2:**

** 输入: s = "abab", p = "ab" ** 输出: [0,1,2] ** 解释:** 起始索引等于 0 的子串是 "ab", 它是 "ab" 的异位词。 起始索引等于 1 的子串是 "ba", 它是 "ab" 的异位词。 起始索引等于 2 的子串是 "ab", 它是 "ab" 的异位词。

提示:

  • 1 <= s.length, p.length <= 3 * 104

  • s 和 p 仅包含小写字母