描述:给定一个字符串,请你找出其中不含有重复字符的 最长子串 的长度。
输入: s = "abcabcbb"
输出: 3
解释: 因为无重复字符的最长子串是 "abc",所以其
长度为 3。
输入: s = "bbbbb" 输出: 1 解释: 因为无重复字符的最长子串是"b"
,所以其长度为 1。
思路一:利用滑动窗口:类似于一个队列,比如例题中的 abcav,进入这个窗口为 abc 满足题目要求,当再进入 a,队列变成了 abca,这时候不满足要求。所以,我们要移动这个队列,此时的窗口值为bca
即left移动到,b位置,移动到重复值a的后一位。相当于将与当前相同的值的左边全部移出窗口。
时间复杂度:O(n)
完整代码如下:
public int lengthOfLongestSubstring(String s){ HashMap<Character,Integer> map = new HashMap<>(); int max = 0; //最长长度 int left = 0; //滑动窗口最初为零 for(int i = 0;i<s.length();i++){ if(map.containsKey(s.charAt(i))){ //如果包含,则更新left, left = Math.max(left,map.get(s.charAt(i)+1)); //之所以要不能直接取map.get(s.charAt(i))+1是因为当前值可能不包含在有效字段里面 } map.put(s.charAt(i),i);//更新left后,不管原来的 s.charAt(i) 是否在最长子段中,我们都要将 s.charAt(i) 的位置更新为当前的i, //如果包含了,则会把之前的给覆盖掉。 max = Math.max(max,i-left+1); //更新max } return max; }
2021-05-29
原文:https://www.cnblogs.com/liuhuaabcp/p/14826586.html