【CT】LeetCode手撕—3. 无重复字符的最长子串

• 原题链接：3. 无重复字符的最长子串

题目

• 无重复字符的最长子串
  给定一个字符串 s ，请你找出其中不含有重复字符的 **最长 子串 **的长度。
  示例 1:

输入: s = “abcabcbb”
输出: 3
解释: 因为无重复字符的最长子串是 “abc”，所以其长度为 3。

示例 2:

输入: s = “bbbbb”
输出: 1
解释: 因为无重复字符的最长子串是 “b”，所以其长度为 1。

示例 3:

输入: s = “pwwkew”
输出: 3
解释: 因为无重复字符的最长子串是 “wke”，所以其长度为 3。
请注意，你的答案必须是 子串 的长度，“pwke” 是一个子序列，不是子串。

1- 思路

• 题型：哈希表、字符串、滑动窗口
• 需要遍历每个子串，判断当前 位 的元素是否在已出现的子串中重复，若重复则从头开始计数

1-1 模式1：涉及去重判断

• 根据模式1 ——> 需要一个数据结构实现两个方面：
  • 存储已经遍历的字符串
  • 去重操作
    

1-2 模式2：遍历字符串区间

• 根据模式2 ——> 遍历字符串区间 ——> 双指针实现滑动窗口
  

2- 题解

⭐无重复字符的最长子串——题解思路

class Solution {
    public int lengthOfLongestSubstring(String s) {
        // 1. 哈希表去重
        HashSet<Character> hs = new HashSet<>();

        // 2. 双指针
        int right = -1;
        int res = 0;

        // 遍历s
        for(int i = 0 ; i < s.length();i++){

            // 2-2 左指针移动
            if(i!=0){
                hs.remove(s.charAt(i-1));
            }
            // 结果收集
            while(right+1 < s.length() && !hs.contains(s.charAt(right+1))){
                hs.add(s.charAt(right+1));
                right++;
            }
            res = Math.max(res,hs.size());
        }
        return res;
    }
}

3- ACM实现

package Daily_LC.Month6_Week1.Day84;

import java.util.HashSet;
import java.util.Scanner;


public class lengthOfLongestSubstring {


    public static int longestSubstring(String s){
        // 1 数据结构
        HashSet<Character> hs = new HashSet<>();

        // 2- 双指针
        int right = -1;
        int res = 0;

        // 2-1 遍历
        for(int i = 0 ; i < s.length();i++){
            // 2-2 左指针移动
            if(i!=0){
                hs.remove(s.charAt(i-1));
            }
            // 2-3 for 遍历
            while(right+1<s.length() && !hs.contains(s.charAt(right+1))){
                hs.add(s.charAt(right+1));
                right++;
            }
            res = Math.max(res,hs.size());
        }
        return res;
    }


    // 输入一个字符串
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String str = sc.nextLine();
        System.out.println(longestSubstring(str));
    }

}