首页 > itarticle > 3. longest substring without repeating characters 实现 参考资料

3. longest substring without repeating characters 实现 参考资料

admin 11月 14, 2020 0

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.

求出字符串中不包含重复字符的最大连续字符串的长度。

实现

  • java

暴力遍历求解

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
 
if (s == null || s.length() == 0){
      return 0;
    }
    int max = 0;
    int temp = 0;
    int len = s.length();
    char[] ary = s.toCharArray();
    Set<Character> res = new HashSet<>();
    for (int i = 0; i < len; i++){
      char out  = ary[i];
      if (!res.contains(out)){
        temp++;
        res.add(out);
        for (int j = i+1; j < len;j++){
          char in  = ary[j];
          if (!res.contains(in)){
            temp ++;
            res.add(in);
          } else {
            break;
          }
        }
        if (temp > max){
          max = temp;
        }
        temp = 0;
        res.clear();
      } else {
        break;
      }
    }
    return max;

讨论区其他答案

  • java

HashMap求解

1
2
3
4
5
6
7
8
9
10
11
12
13
 
public int (String s) {
        if (s.length()==0) return 0;
        HashMap<Character, Integer> map = new HashMap<Character, Integer>();
        int max=0;
        for (int i=0, j=0; i<s.length(); ++i){
            if (map.containsKey(s.charAt(i))){
                j = Math.max(j,map.get(s.charAt(i))+1);
            }
            map.put(s.charAt(i),i);
            max = Math.max(max,i-j+1);
        }
        return max;
    }
  • java

双指针

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
 
public int (String s) {
        char[] v=s.toCharArray();
        int length=-1;
        int max=0;
        for(int i=0;i<v.length;i++){
            if(i==0){
                length=1;
                max=1;
            }else{
                int ind=-1;
                for(int j=i-1;j>=i-length;j--){
                    if(v[i]==v[j]){
                        ind=j-(i-length);
                        break;
                    }
                }
                if(ind==-1){
                    length=length+1;
                }else{
                    length=length-ind;
                }
                max=max>length?max:length;
            }
        }
    return max;
}

参考资料

微海报分享

近期文章

近期评论

标签

热门

文章归档

分类目录

功能