算法題之求最大不重複子串的個數(滑動視窗)

題目描述

給定一個字元串，請你找出其中不含有重複字元的 最長子串 的長度。

示例 1:

輸入: “abcabcbb”

輸出: 3

解釋: 因為無重複字元的最長子串是 “abc”，是以其長度為 3。

示例 2:

輸入: “bbbbb”

輸出: 1

解釋: 因為無重複字元的最長子串是 “b”，是以其長度為 1。

示例 3:

輸入: “pwwkpw”

輸出: 3

解釋: 因為無重複字元的最長子串是 “kpw”，是以其長度為 3。

題解(滑動視窗)

以輸入: "pwwkpw"為例

滑動視窗思路分析:利用HashMap的鍵唯一性

• (1)當我們判斷字元串目前字元在HashMap中key中未曾出現過:
  • 則直接将其加入到HashMap中:其中鍵(key)即為目前的字元(Character),值(value)即為該字元在String字元串的索引
  • 其中此時的最大字元串的最大長度(maxLength)即為目前索引 – left(初始值為0) + 1;第一次添加p,則maxLength = 1;
• (2)若依次添加字元,字元key值未在HashMap中出現過,則一直将其加入HashMap中,故p,w的maxLength = 1 – left + 1 = 2;
• (3)若添加字元,目前key值在HashMap中出現過,根據HashMap的鍵唯一性:
  • 首先我們需要更新此時的left指針變量,即更新視窗的滑動:
  • 開始時,left位于0位置,此時,選擇之前的left指針和目前key值字元的位置 + 1,即移除重複出現的字元,取兩者的最大值為新的left指針
  • 故此時的left為2,此時再将目前鍵值加入HashMap集合中時,替換之前的value值,即更新w的索引位置,而此時的maxLength,即為之前的maxLength[p,w = 2]和現在的i – left + 1 = 1[w]的最大值

  • 接着,也是同上思路,當周遊到p字元時,需要更新left的位置:因為先前的left索引大于此時p之前的索引 + 1,則視窗不發生偏移

    maxLength = [p,w] vs [w,k,p] = 3;

  • 最後到w,更新left位置為k的位置,此時maxLength = [w,k,p] vs [k,p,w] = 3;
• (4)故最終的maxLength = 3;即最大的非重複子串的長度為:3.

圖解過程

代碼實作

public static void main(String[] args) {
        String str = "pwwkpw";
        LongestSubString2 solution = new LongestSubString2();
        int maxLength = solution.lengthOfLongestSubstring(str);
        System.out.println("最大不重複的子字元串的長度為: " + maxLength);
    }

    private int lengthOfLongestSubstring(String s) {
        //定義該字元串的長度為n
        int n = s.length();
        //若長度小于等于1,則maxLength即為字元串本身的長度,直接傳回
        if (n <= 1) {
            return n;
        }
        //定義maxLength作為最大不重複子串的長度
        int maxLength = 0;
        //定義滑動視窗的左指針的變量,初始化為0
        int left = 0;
        //定義一個HashMap進行存儲
        HashMap<Character,Integer> hashMap = new HashMap<>();
        for (int i = 0; i < n; i++) {
            if (hashMap.containsKey(s.charAt(i))) {
                //如果目前key值在hashmap中已經存在
                //則更新left指針為之前的出現的指針向右平移一位
                left = Math.max(left, hashMap.get(s.charAt(i)) + 1);
            }
            //将該鍵值添加到hashmap集合中
            hashMap.put(s.charAt(i),i);
            maxLength = Math.max(maxLength,i - left + 1);
        }
        //傳回最大值maxLength
        return maxLength;
    }