剑指offer 48 最长不含重复字符的子字符串

package com.example.lettcode.offer;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

/**
 * @Class LengthOfLongestSubstring
 * @Description 剑指offer 48 最长不含重复字符的子字符串
 * 请从字符串中找出一个最长的不包含重复字符的子字符串，计算该最长子字符串的长度。
 * <p>
 * 示例 1:
 * 输入: "abcabcbb"
 * 输出: 3
 * 解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。
 * <p>
 * 示例 2:
 * 输入: "bbbbb"
 * 输出: 1
 * 解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。
 * <p>
 * 示例 3:
 * 输入: "pwwkew"
 * 输出: 3
 * 解释: 因为无重复字符的最长子串是?"wke"，所以其长度为 3。
 * ?    请注意，你的答案必须是 子串 的长度，"pwke"?是一个子序列，不是子串。
 * @Author
 * @Date 2020/7/18
 **/
public class LengthOfLongestSubstring {
    /**
     * 解法1:利用滑动窗口+双指针
     */
    public static int lengthOfLongestSubstring(String s) {
        if (s == null) return 0;
        if (s.length() <= 1) return s.length();
        int p = 0, q = 1;
        int ans = 0;
        // 方式1:--start 利用哈希
       /* char[] chars = s.toCharArray();
        List<Character> characterList = new LinkedList<>();
        characterList.add(chars[0]);
        while (p < s.length() && q < s.length()) {
            char ch = chars[q];
            // s[p..q-1]中包含字符s[q]时,p指针++
            while (characterList.contains(ch)) {
                p++;
                characterList.remove(0);
            }
            characterList.add(chars[q]);
            q++;
            ans = Math.max(ans, (q - p));
        }*/
        // 方式1:--end
        // 方式2:--start
        // 直接判断字符串是否包含某字符
        while (p < s.length() && q < s.length()) {
            char ch = s.charAt(q);
            // s[p..q-1]中包含字符s[q]时,p指针++
            while (s.substring(p, q).indexOf(ch) != -1) {
                p++;
            }
            q++;
            ans = Math.max(ans, (q - p));
        }
        // 方式2:--end
        return ans;
    }

    public static void main(String[] args) {
        String s = "abcabcbb";
        int ans = lengthOfLongestSubstring(s);
        System.out.println("LengthOfLongestSubstring demo01 result:" + ans);

        s = "bbbbb";
        ans = lengthOfLongestSubstring(s);
        System.out.println("LengthOfLongestSubstring demo02 result:" + ans);

        s = "pwwkew";
        ans = lengthOfLongestSubstring(s);
        System.out.println("LengthOfLongestSubstring demo03 result:" + ans);

        s = "dvdf";
        ans = lengthOfLongestSubstring(s);
        System.out.println("LengthOfLongestSubstring demo04 result:" + ans);
    }
}

剑指offer 48 最长不含重复字符的子字符串

原文：https://www.cnblogs.com/fyusac/p/13336514.html