LeetCode从零刷起 (3. Longest Substr

最近好久没有更新博客了，因为博主最近忙于学校的一些学业工作。大三下学期嘛，还是挺忙的-，-。
下面我们来看一下这道题：

Given a string, find the length of the longest substring without repeating characters.
Examples:
Given "abcabcbb", the answer is "abc", which the length is 3.
Given "bbbbb", the answer is "b", with the length of 1.
Given "pwwkew", the answer is "wke", with the length of 3. Note that the answer must be a substring, "pwke" is a subsequence and not a substring.

题目简介

这道题输入是一个字符串s，然后让我们返回最长不重复子串的长度。

知识要点：

1.ASCⅡ字符一共有128个，一般情况下，计算机最多只能表示128个不同的character。
2.Sliding window的思想。

解题思路：

首先我们很容易想到用一个128位的数组来存储子串中是否出现过了某个字符，我们用一个布尔型数组表示：<code>bool used[128];</code>
接下来就是对子串的寻找过程了，首先是暴力算法：

Approach 1: Brute Force

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        bool isIn[128];
        int i, j, max = 0, tmp;
        string sub;
        for (i=0; i<s.length(); ++i){
            for (int k=0; k<128; ++k)
                isIn[k] = false;
            for (j=i; j<s.length(); ++j){
                if (isIn[int(s[j])] == false){
                    isIn[int(s[j])] = true;
                    tmp = j-i+1;
                    if (tmp > max)
                        max = tmp;
                }
                else
                    break;
            }
        }
        return max;
    }
};

时间复杂度: O(n^2)。
brute force是一种最容易想到的naïve algorithm了，但是根据我们的做题经验（-，-），这题肯定还有更优化的算法，于是我们想到了sliding window的思想：

Aproach 2: Sliding Window

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        int i=0, j=0, max = 0, n = s.length();
        bool used[128] = {0};
        while (i < n && j < n){
            if (used[int(s[j])] == 0){
                used[int(s[j++])] = true;
                max = (j-i) > max? (j-i):max;
            }
            else
                used[int(s[i++])] = false;
        }
        return max;
    }
};

时间复杂度: O(2n) = O(n)
Sliding Window（滑动窗口）的思想：

设置一个窗口左边界和一个窗口右边界。
重复下列过程直到字符串末尾{
符合条件时，窗口右边界移动扩增；
不符合条件时：窗口左边界移动内缩。
}

在执行该算法的同时，注意改变<code>used[]</code>数组的元素值从而记录当前子串是否存在某一character。同时注意更新最长长度max。最后返回max即可。