[Leetcode] Longest Substring Without Repeating Characters 题解

发表于 | 分类于 | 阅读次数:
字数统计: 227 字

题目链接:https://leetcode.com/problems/longest-substring-without-repeating-characters/#/description

题意

给出一个字符串，求出其中最长的不重复字符串的长度

题解

  • 用一个数组记录每个字符出现的索引值，没有出现的为零
  • 设定一个开始指针表示计算字符开始的地方（初始值为0），这样每次扫描到一个字符的时候，先更新这个指针。然后计算开始指针到扫描的地方的字符串长度更新结果值。
  • 最后更新字符出现的索引值

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        int a[256];
        memset(a,0,sizeof(a));
        int ans=0,num=0,start=0;
        for(int i=1;i<=s.size();i++)
        {
            start=start>a[s[i-1]]?start:a[s[i-1]];
            num=i-start;
            ans=ans>num?ans:num;
            a[s[i-1]]=i;
        }
        ans=ans>num?ans:num;
        return ans;
    }
};