小米日常实习 二面

原题链接:
https://leetcode.cn/problems/longest-substring-without-repeating-characters/description/

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
    public int lengthOfLongestSubstring(String s) {
        int n = s.length();
        char [] cs = s.toCharArray();
        // 用作滑动窗口 字符 以及 出现的位置
        HashMap<Character,Integer> hash = new HashMap<>();
        int left = 0;
        int ans = 0;
        for(int i = 0; i < n; i++){
            if(hash.containsKey(cs[i])){
                left = Math.max(hash.get(cs[i]) + 1,left);
            }

            // 更新 字符出现的 最后一个位置
            hash.put(cs[i],i);
            // i 是当前位置 已经包括在窗口内了 所示 i - left + 1
            ans = Math.max(ans,i - left + 1);
        }

        return ans;
    }
}