LeetCode 3. Longest Substring Without Repeating Characters (无重复的最长子串)

深碍√TFBOYSˉ_ 2022-05-14 09:17 227阅读 0赞

题目描述：

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

示例1：

  1. 输入: "abcabcbb"
  2. 输出: 3 
  3. 解释: 无重复字符的最长子串是 "abc"，其长度为 3。

示例2：

  1. 输入: "bbbbb"
  2. 输出: 1
  3. 解释: 无重复字符的最长子串是 "b"，其长度为 1。

示例3：

  1. 输入: "pwwkew"
  2. 输出: 3
  3. 解释: 无重复字符的最长子串是 "wke"，其长度为 3。
  4.      请注意，答案必须是一个子串，"pwke" 是一个子序列 而不是子串。

Accepted C++ Solution: (From leetcode.com )

  1. class Solution {
  2. public:
  3.     int lengthOfLongestSubstring(string s) {
  4.         vector<int> dict(256,-1);
  5.         int maxlen = 0, start = -1;
  6.         for (int i = 0; i != s.length(); i++) {
  7.             if (dict[s[i]] > start)    //此时字符重复出现      
  8.                 start = dict[s[i]];    //更新起始位置
  9.             dict[s[i]] = i;
  10.             maxlen = max(maxlen, i-start);    //不论是否出现重复,i-start都是字符串长度
  11.         }
  12.         return maxlen;
  13.     }
  14. };

很巧妙的一种方法，和哈希表很像，不过使用char来作为下标。

发表评论

表情：
评论列表 （有 0 条评论，227人围观）

还没有评论，来说两句吧...

相关阅读