https://leetcode-cn.com/problems/longest-substring-without-repeating-characters

一 题目

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

示例 1: 输入: s = “abcabcbb” 输出: 3 解释:

因为无重复字符的最长子串是 “abc”，所以其长度为 3。

示例 2: 输入: s = “bbbbb” 输出: 1 解释:

因为无重复字符的最长子串是 “b”，所以其长度为 1。

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

请注意，你的答案必须是 子串 的长度，”pwke” 是一个子序列，不是子串。

示例 4: 输入: s = “”

输出: 0

提示： 0 <= s.length <= 5 * 104

s 由英文字母、数字、符号和空格组成

二 题解

这题的要求是，字符串的子串是一个没有重复字符的串。
假如：字符串为“acbdbeface”
从头开始找，a->ac->acb->acbd
第一次出现重复：acbdb，重复的字符是b，此时最长字符串长度为 4
因此，下一次查找为：dbe。
很明显了，这就是一个双指针的滑动窗口问题，利用双指针来控制滑动窗口大小，计算窗口的最大值。
没有重复字符的时候，那么子串的长度是在递增的
因此在无重复字符的时候，要计算此时字符串长度是否是当前的最大值。
出现重复字符的时候，那么子串的长度肯定是减小的
因此在出现重复字符的时候，只需要移动子串头部位置到新的位置（即子字符串中哪个位置是与比较的字符重复的）。

import java.util.HashMap;
import java.util.Map;
class Solution {
    public int lengthOfLongestSubstring(String s) {
        if(s.length()<2){
            return s.length();
        }
        char[] arrays = s.toCharArray();
        return doFind(arrays);
    }
    private int doFind(char[] arrays){
        int length = arrays.length;
        Map<Character,Integer> map = new HashMap<>();
        int start = 0;
        int end = 1;
        int longestLength = 1;
        map.put(arrays[start],start);
        while(end<length){
            // 判断map中是否存在相同的 字符，并且字符的位置位于两个指针之间
            if(map.containsKey(arrays[end])&&(map.get(arrays[end])>=start)){
                /*如果为真，则表示在start到end-1之间有字符与end位置的字符是相同的。*/
                // 获取到该字符的位置,然后该字符后一位为新的子字符串开始位置
                start = map.get(arrays[end])+1;
            }else{
                /* 如果为假，则表示end位置为非重复的字符因此 */
                longestLength = longestLength<(end-start+1)?(end-start+1):longestLength;
            }
            map.put(arrays[end],end);
            end++;
        }
        return longestLength;
    }
    public static void main(String[] args) {
        Solution solution = new Solution();
        String s1 = "abcabcbb";
        System.out.println("预期为3，实际为"+solution.lengthOfLongestSubstring(s1));
        String s2 = "bbbbb";
        System.out.println("预期为1，实际为"+solution.lengthOfLongestSubstring(s2));
        String s3 = "pwwkew";
        System.out.println("预期为3，实际为"+solution.lengthOfLongestSubstring(s3));
        String s4 = "";
        System.out.println("预期为0，实际为"+solution.lengthOfLongestSubstring(s4));
    }
}

也可以使用数组来保存出现过的字符与其最后出现的位置

import java.util.HashMap;
import java.util.Map;
class Solution2 {
    public int lengthOfLongestSubstring(String s) {
        if(s.length()<2){
            return s.length();
        }
        char[] arrays = s.toCharArray();
        return doFind(arrays);
    }
    private int doFind(char[] arrays){
        int length = arrays.length;
        int[] last = new int[256];
        for(int i = 0; i < 256; i++) {
            last[i] = -1;
        }
        int start = 0;
        int end = 1;
        int longestLength = 1;
        last[arrays[start]] = start;
        while(end<length){
            // 判断该字符串是否出现过，并且出现的位置在start之后
            if(last[arrays[end]]>=start){
                /*如果为真，则表示在start到end-1之间有字符与end位置的字符是相同的。*/
                // 获取到该字符的位置,然后该字符后一位为新的子字符串开始位置
                start = last[arrays[end]]+1;
            }else{
                /* 如果为假，则表示end位置为非重复的字符因此 */
                longestLength = longestLength<(end-start+1)?(end-start+1):longestLength;
            }
            last[arrays[end]] = end;
            end++;
        }
        return longestLength;
    }
    public static void main(String[] args) {
        Solution2 solution = new Solution2();
        String s1 = "abcabcbb";
        System.out.println("预期为3，实际为"+solution.lengthOfLongestSubstring(s1));
        String s2 = "bbbbb";
        System.out.println("预期为1，实际为"+solution.lengthOfLongestSubstring(s2));
        String s3 = "pwwkew";
        System.out.println("预期为3，实际为"+solution.lengthOfLongestSubstring(s3));
        String s4 = "";
        System.out.println("预期为0，实际为"+solution.lengthOfLongestSubstring(s4));
    }
}