JZ48 最長不含重覆字元的子字元串

描述

請從字元串中找出一個最長的不包含重覆字元的子字元串，計算該最長子字元串的長度。

示例1
輸入："abcabcbb"
返回值：3
說明：因為無重覆字元的最長子串是"abc"，所以其長度為 3。  

方法1

思路

維護一個數組，想裡面添加元素，直至出現第一個重覆元素位置，計算數組長度作為一次結果
將每一個元素都作為開始元素，利用兩次for，將全部不重覆子字元串全部計算出來，取出最大數

代碼

int max = Integer.MIN_VALUE;
        List<Character> tmp = new ArrayList<>();
        if(s == null && s.length() == 0) return 0;
        for(int i = 0; i < s.length(); i++) {
            for(int j = i; j < s.length(); j++) {
                if(tmp.contains(s.charAt(j))) break;
                tmp.add(s.charAt(j));
            }
            max = Math.max(max, tmp.size());
            tmp.clear();
        }
        return max;

方法2

思路

既然要找一段連續子串的內不重覆的長度，我們可以使用滑動視窗，保證視窗內都是不重覆的，然後視窗右界不斷向右滑，如果視窗內出現了重覆字元，說明新加入的元素與之前的重覆了，只需要視窗左界也向右收縮就可以保證視窗內都是不重覆的。

具體做法:
step 1：構建一個哈希表，用於統計字元元素出現的次數。
step 2：視窗左右界都從字元串首部開始，每次視窗優先右移右界，並統計進入視窗的元素的出現頻率。
step 3：一旦右界元素出現頻率大於1，就需要右移左界直到視窗內不再重覆，將左邊的元素移除視窗的時候同時需要將它在哈希表中的頻率減1，保證哈希表中的頻率都是視窗內的頻率。
step 4：每輪迴圈，維護視窗長度最大值。

代碼

HashMap<Character, Integer> map = new HashMap<>();
        int res = 0;
        for (int left = 0, right = 0; right < s.length(); right++) {
            //標記重覆的元素
            if (map.containsKey(s.charAt(right))) {
                //視窗右移進入哈希表統計出現次數
                map.put(s.charAt(right), map.get(s.charAt(right)) + 1);
            } else {
                map.put(s.charAt(right), 1);
            }

            //左邊界向右移知道沒有重覆元素
            while (map.get(s.charAt(right)) > 1) {
                map.put(s.charAt(left), map.get(s.charAt(left++)) - 1);
            }

            //維護子字元串最大長度
            res = Math.max(res, right - left + 1);
        }

        return res;

整體代碼

package mid.JZ48最長不含重覆字元的子字元串;

import java.util.*;


public class Solution {
    /**
     * 代碼中的類名、方法名、參數名已經指定，請勿修改，直接返回方法規定的值即可
     *
     * 
     * @param s string字元串 
     * @return int整型
     */
    public int lengthOfLongestSubstring (String s) {
        // write code here
        //方法1
        /*int max = Integer.MIN_VALUE;
        List<Character> tmp = new ArrayList<>();
        if(s == null && s.length() == 0) return 0;
        for(int i = 0; i < s.length(); i++) {
            for(int j = i; j < s.length(); j++) {
                if(tmp.contains(s.charAt(j))) break;
                tmp.add(s.charAt(j));
            }
            max = Math.max(max, tmp.size());
            tmp.clear();
        }
        return max;*/

        //方法2
        HashMap<Character, Integer> map = new HashMap<>();
        int res = 0;
        for (int left = 0, right = 0; right < s.length(); right++) {
            //標記重覆的元素
            if (map.containsKey(s.charAt(right))) {
                //視窗右移進入哈希表統計出現次數
                map.put(s.charAt(right), map.get(s.charAt(right)) + 1);
            } else {
                map.put(s.charAt(right), 1);
            }

            //左邊界向右移知道沒有重覆元素
            while (map.get(s.charAt(right)) > 1) {
                map.put(s.charAt(left), map.get(s.charAt(left++)) - 1);
            }

            //維護子字元串最大長度
            res = Math.max(res, right - left + 1);
        }

        return res;
    }

    public static void main(String[] args) {
        System.out.println(new Solution().lengthOfLongestSubstring("Kzz8"));
    }
}