LeetCode T3 无重复字符的最长字串

简单的字符串，学习滑动窗口的思想。

题目

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

示例 1:

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

滑动窗口

最初的想法是对每个字母s[i]，遍历s[i]到s[n]，记录最短的子串。

但是可以优化的点在于，可以省去一些重复的检查。

比如 s = “abcdeab”

当检测出abcde不重复，遇到a停止检测，对b进行检测，bcde是不需要重复检测的。因此把它想象成一个可以滑动的窗口就可以减少开销。

然后想到，用hashmap存储窗口里的值，这样每次检查containskey的时候开销是O(1)。

代码

class Solution {
    public int lengthOfLongestSubstring(String s) {
        char[] ch = s.toCharArray();
        HashMap<Character, Integer> hashmap = new HashMap<>();
        int head=0,tail=0,max=0;
        while(head<s.length() && tail < s.length())
        {

            if (!hashmap.containsKey(ch[tail]))
            {
                hashmap.put(ch[tail],tail);
                tail++;
                 if (tail-head > max)
                max=tail-head;

            }
            else {
                hashmap.remove(ch[head]);
                head++;
            }
        }
        return max;
    }
}

优化

发现自己不能只追求做出来了……执行时间超过76% 内存竟然只超过5%

2333

所以不需要新建一个charArray来存。

java String中的charAT() 方法就可以取出来某个索引位置的值。