3. Longest Substring Without Repeating Characters

发表于 | 分类于

每日一题 2019 - 02 - 28

题目：

Given a string, find the length of the longest substring without repeating characters.

Example 1:

1
2
3
Input: "abcabcbb"
Output: 3 
Explanation: The answer is "abc", with the length of 3.

Example 2:

1
2
3
Input: "bbbbb"
Output: 1
Explanation: The answer is "b", with the length of 1.

Example 3:

1
2
3
4
Input: "pwwkew"
Output: 3
Explanation: The answer is "wke", with the length of 3. 
             Note that the answer must be a substring, "pwke" is a subsequence and not a substring.

解法：

这个题让我们找出某字符串中不重复的最长序列，思路很简单：使用哈希的方法，建立一个数组把每个字符出现的次数投影到对应数组中，对于次数超过1次的序列进行抛弃，二重循环即可解决问题。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        int n = s.size();
        string test = "";
        string temp = "";
        int arr[500] = {0};
        if( s.size() == 0 )
        {
            return 0 ;
        }
        for(int j = 0 ; j < n ; j ++)
        {
            for(int i = j ; i < n ; i ++)
            {
                if(arr[s[i]-' '] == 0)
                {
                    test += s[i] ;
                    arr[s[i]-' '] ++;
                    if(test.size() > temp.size())
                    {
                        temp = test ;
                    }
                }
                else
                {
                    if(test.size() > temp.size())
                    {
                        temp = test ;
                    }
                    test = "" ;
                    for(int k = 0 ; k < 500 ; k ++ )
                    {
                        arr[k] = 0 ;
                    }
                    break ;
                }   
            }   
        }
        return temp.size() ;
    }
};
0%
undefined