Leetcode--無重複字元的最長子串

無重複子串的最長子串

• 題目描述：
• 分析：
• 代碼：
• 注意事項：

題目描述：

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

示例 1:

輸入: “abcabcbb”

輸出: 3

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

示例 2:

輸入: “bbbbb”

輸出: 1

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

示例 3:

輸入: “pwwkew”

輸出: 3

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

請注意，你的答案必須是 子串 的長度，“pwke” 是一個子序列，不是子串。

不成文的小規則：子序列預設是不連續的，子串，子數組預設是連續的

分析：

剛看到這個題的時候看到要求是求最長子串，最長兩個字讓我第一反應是用動态規劃來解決這個題。

我剛開始想到的定義dp[i]表示以s[i]字元結尾的的最長子串，遞推公式是：如果dp[i-1]的最長子串中沒有s[i]，dp[i] = dp[i-1]+1，如果dp[i-1]中的最長子串有s[i]…

我發現如果要使用動态規劃來做這個題的話，每個dp[i]中還需要維護一組資料來儲存以s[i]結尾的最長子串，想到這我就沒有繼續往動态規劃方向思考，因為子串即數組中連續的資料，腦海中又立即想到使用滑動視窗的方法。

滑動視窗思路：

用一個左指針一個右指針指向s[0]，右指針開始往後走，如果s[right]在s[left]—s[right-1]中出現過即s[x]，左指針就指向s[x+1]處，右指針++，繼續周遊，如果s[right]沒有在s[left]–s[right-1]中出現過，就把s[right]及其位置加入到my_map中右指針++繼續周遊

在這個過程中記錄子串的長度，最後傳回的是長度最大值

這樣的話程式中必須要有一個記錄子串和每個字元的位置的資料結構，用unordered_map<char,int>就很合适，Key域為字元，Value域為該字元的位置，因為左指針要根據重複出現的字元的位置移動。

代碼：

int lengthOfLongestSubstring(string s) 
    {
        int n = s.size();
        unordered_map<char,int> my_map(n);
        if(n == 1) return 1; //如果字元串中隻有一個數，直接傳回1
        int left = 0;
        int right =1;
        my_map.insert(pair<char,int>(s[0],0));//先把s[0]及其位置放到my_map中
        int res = 0;
        int num = 1; 
        while(right < n)
        {
           int pos = 0;
            while(right < n)
            {
                if(!(my_map.count(s[right]))) //如果s[left]---s[right-1中沒出現過]s[right]
                {
                    num++;
                    my_map.insert(pair<char,int>(s[right],right));
                    right++;
                }
                else
                {
                    unordered_map<char,int>::iterator it = my_map.find(s[right]);//找到出現s[right]的位置it
					pos = it->second;//取出出現重複的位置
					//将s[left]--s[pos]從my_map中删除
					for(int i = left;i <= pos;i++)
					{
						my_map.erase(s[i]);
					}
					my_map.insert(pair<char,int>(s[right],right));//插入s[right]
                    num = num - (pos-left);//計數數量發生變更！！！
                    left = pos+1;
					right++;
                }
                res = max(res,num);
            }
			
        }
        return res;
    }
           

注意事項：

一定要注意當我們把視窗縮小的時候，此時的子串長度要發生改變，num = num-(pos - left)，改變後再繼續周遊