LeetCode03 无重复字符的最长字串

题目描述

给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。

样例

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

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

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

算法分析

双指针算法

来看这样的情况

用什么来记入[j~i]之间每个元素的个数呢？哈希表

时间复杂度$O(n+n)=O(n)$

最坏的情况，也是i指针n次，j指针n次

Java代码

class Solution {
    public int lengthOfLongestSubstring(String s) {
        HashMap<Character, Integer> map = new HashMap<Character, Integer>();
        int ans = 0;
        for(int i = 0,j = 0;i < s.length(); i++){
            char c = s.charAt(i);
            map.put(c, map.getOrDefault(c, 0) + 1);

            while(map.get(c) > 1){ //新进的i可能带来重复
                //j走
                //让后，让其减一
                map.put(s.charAt(j), map.get(s.charAt(j)) - 1);
                j++;
            }

            ans = Math.max(ans, i - j + 1);

        }

        return ans;
    }
}

• j只能往前走

• 只有可能是新进的i导致的重复，所以判断是while(map.get(c) > 1)