leetcode【3】Longest Substring Without Repeating Characters

滑动窗口：尾部处理更为重要

tags

**hash-table | two-pointers | string | sliding-window

**

question

Given a string, find the length of the longest substring without repeating characters.

Example:

Input: “abcabcbb”
Output: 3
Explanation: The answer is “abc”, with the length of 3.

Input: “bbbbb”
Output: 1
Explanation: The answer is “b”, with the length of 1.

Input: “pwwkew”
Output: 3
Explanation: The answer is “wke”, with the length of 3.
Note that the answer must be a substring, “pwke” is a subsequence and not a substring.

myAnswer

思路： 建一个hash表遇到表中不存在的字符【存进去】，判断窗口长度并取最大长度， 遇到表中存在的字符则重新把窗口左标签设立，并把左标签之前即窗口外的字符去掉，则重新出现一个窗口。

//java
class Solution {
    public int lengthOfLongestSubstring(String s) {
        int flag = 0,max = 0,single = 0;
        HashMap<Character,Integer> map = new HashMap<>();
        if(s.length() == 0){
            return 0;
        }
        map.put(s.charAt(0),0);
        for(int i = 1 ; i < s.length() ; i++){
            if(!map.containsKey(s.charAt(i))){
                map.put(s.charAt(i),i);
                if(i - flag > max){
                    max = i - flag;
                }
            }else{
                flag = map.get(s.charAt(i))+1;
                map.replace(s.charAt(i), i);
                for(int j = single ; j < flag;j++){
                    map.remove(s.charAt(j),j);
                }
                single = flag;
            }
        }
        
        return max + 1;
    }
}

** 改进的方法：**
直接弄左右标签,right标签添加数据，left标签删除数据后一种方法更简洁。

//java
public class Solution {
    public int lengthOfLongestSubstring(String s) {
        int res = 0, left = 0, right = 0;
        HashSet<Character> t = new HashSet<Character>();
        while (right < s.length()) {
            if (!t.contains(s.charAt(right))) {
                t.add(s.charAt(right++));
                res = Math.max(res, t.size());
            } else {
                t.remove(s.charAt(left++));
            }
        }
        return res;
    }
}