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"));
    }
}

標籤：其他

上一篇：Java7提供的Fork/Join框架實作高并發程式，你會使用嗎？

下一篇：【K哥爬蟲普法】老鐵需要車牌靚號嗎？判刑的那種