3. Longest Substring Without Repeating Characters 【Medium】

avatar 2020年08月29日15:01:47 5 1961 views
博主分享免费Java教学视频,B站账号:Java刘哥

Question

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

Example 1:

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

Example 2:

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

Example 3:

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.

 

 

My Answer 1

暴力求解法,不推荐

class Solution {
    public int lengthOfLongestSubstring(String s) {
        int max = 0;
        for(int i=0; i<s.length(); i++) {
            Set<Character> set = new HashSet<>();
            for(int j=i; j<s.length(); j++) {
                char c = s.charAt(j);
                if(!set.contains(c)) {
                    set.add(c);
                    max = Math.max(max, set.size());
                } else {
                    break;
                }
            }
        }
        return max;
    }
}

 

My Answer 2

将上面两次循环改成一层,依然使用 set 来放连续数据,只不过这次求最大长度使用的是  j - i

class Solution {
    public int lengthOfLongestSubstring(String s) {
        int max = 0, i = 0, j = 0;
        int n = s.length();
        Set<Character> set = new HashSet<>();
        while(i < n && j < n) {
            // j往前走
            if(!set.contains(s.charAt(j))) {
                set.add(s.charAt(j));
                j++;
                // max 即是 [i, j] 的范围
                max = Math.max(max, j-i);
            }
            // i 往前走
            else {
                set.remove(s.charAt(i));
                i++;
            }
        }
        return max;
    }
}

 

  • 微信
  • 交流学习,有偿服务
  • weinxin
  • 博客/Java交流群
  • 资源分享,问题解决,技术交流。群号:590480292
  • weinxin
avatar

发表评论

avatar 登录者:匿名
匿名评论,评论回复后会有邮件通知

  

已通过评论:0   待审核评论数:0