LeetCode題解 || Longest Substring Without Repeating Characters (O(n)算法)問題

LeetCode題解 || Longest Substring Without Repeating Characters (O(n)算法)問題

problem：

Given a string, find the length of the longest substring without repeating characters. 
For example, the longest substring without repeating letters for "abcabcbb" is "abc", 
which the length is 3. For "bbbbb" the longest substring is "b", with the length of 1.

（1）尋找子串，要做一次遍歷。

（2）暴力破解法，檢查每一個子串，利用hash table的映射思想，開一個數組，下標為字符的ASCII碼，由於沒有說明字符串的類型，可以采取一些措施壓縮hash table的大小。暴力破解法的最壞時間復雜度為O(n*n)

（3）發現一個O（n）的算法，很贊

其實，這裡很多工作都是重復的、無用的。
看一個例子：
S="abbdeca"。
t1="abbdeca"，t1[1]==t1[2]。
t2="bbdeca"，t2[0]==t2[1]。
t3="bdeca"，一直掃描到最後。
t4="deca"、t5、t6、t7都同上。
我們在處理t1的時候已經掃描到了s[2]，然後處理t3的時候掃描了s[2]到s[6]，這兩個子串已經掃描完了整個母串。
換言之，能使得子串停止掃描的位置只有兩處：1.s[2]；2.s[6](結尾)。
對於另一個例子S="aaab"，能使子串停止掃描的位置分別是：s[1],s[2],s[3](結尾)。


所以我們可以考慮只掃描母串，直接從母串中取出最長的無重復子串。
對於s[i]：
1.s[i]沒有在當前子串中出現過，那麼子串的長度加1；
2.s[i]在當前子串中出現過，出現位置的下標為j，那麼新子串的起始位置必須大於j，為了使新子串盡可能的長，所以起始位置選為j+1。

code：

說明：注釋的解法復雜度為O（n*n）,沒注釋的位O（n）

#include 
#include 
#include 

using namespace std;
/*
class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        int a[100]; //壓縮hash table
        memset(a,0,sizeof(int)*100);
        int length = s.size();
        int index=0;
        int max=0;
        for(int i=0;iindex)?max:index;
            index=0;
            if(j==length-1) //這裡也有一個小技巧，可以有效降低時間復雜度
                break;
        }
        return max;
    }
};
*/
class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        int locs[256];//保存字符上一次出現的位置
        memset(locs, -1, sizeof(locs));

        int idx = -1, max = 0;//idx為當前子串的開始位置-1
        for (int i = 0; i < s.size(); i++)
        {
            if (locs[s[i]] > idx)//如果當前字符出現過，那麼當前子串的起始位置為這個字符上一次出現的位置+1
            {
                idx = locs[s[i]];
            }

            if (i - idx > max)//這裡是關鍵！！！！！！！！！
            {
                max = i - idx;
            }

            locs[s[i]] = i;
        }
        return max;
    }
};
int main()
{
    string str = "abcdab";
    Solution mysolution;
    cout<