1. 题目描述

Given a string, find the length of the longest substring without repeating characters.

Example 1:

Input: "abcabcbb"
Output: 3 
Explanation: The answer is "abc", with the length of 3. 

Example 2:

Input: "bbbbb"
Output: 1
Explanation: The answer is "b", with the length of 1.

Example 3:

Input: "pwwkew"
Output: 3
Explanation: 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.

2. 初解

暴力遍历每一个子字符串,依次以每一个字符作为头部遍历可能的子字符串,一旦遇到重复字符就跳出循环,以下一个字符作为头部。

关于如何记录是否出现重复字符,可以建立一个大小为128的int数组并初始化为全0,每遇到一个字符,就将该数组下以该字符为索引的元素置1,而每次向后遍历字符的时候只需要先判断这个字符对应的数组元素是否为1就可以判断之前是否出现过这个元素了。

代码如下:

#include <stdio.h>

int lengthOfLongestSubstring(char* s) {
    char* tmp = s;  // tmp指针指向当前子序列的头字符
    char* ptr = tmp;
    int arr[128] = { 0 };
    int res = 0, dummyRes = 0;

    for(; *tmp != '\0'; tmp++, dummyRes = 0) {
        for(ptr = tmp; (arr[*ptr] != 1) && (*ptr != '\0'); ptr++) {
            arr[*ptr] = 1;
            dummyRes += 1;
        }
        if(dummyRes > res)
            res = dummyRes;
        for(int i = 0; i < 128; i++)
            arr[i] = 0;
    }

    return res;
}

int main(int argc, char const *argv[])
{
    char arr[] = "abcuiuuuu";
    printf("%d\n", lengthOfLongestSubstring(arr));
    return 0;
}

3. 代码优化

LeetCode的solution里讲了一种名叫滑动窗口的方法,这种方法在数组和字符串的题中会比较经常的遇到。

滑动窗口其实和我之前的方法比较类似。回顾我之前的解法,解法中使用了两层循环以暴力遍历所有子字符串。但其实在遇到重复字符的时候没必要跳出循环直接让下一个字符当头节点从头开始,这样其实做了很多不必要的工作。

举个例子,对于下面这个字符串"abcdecd",以a为头部遍历子字符串,可以看出直到遍历到字符串"abcde"都没有问题,但下一个字符是'c',出现了重复。我原来的解法是记录下当前的最长子字符串的长度5然后跳出循环,然后以'b'为头节点重新开始依次遍历'bc' 'bcd' 'bcde'等,但其实可以想到,以'b'为头部的子字符串长度一定不可能比'a'为头部的最长长度还长,因为重复的'c'也在里面。所以滑动窗口解法的精髓就在于记录下一个逻辑上的窗口,有left和right边界,在right边界发现一个重复字符的时候,right不动而让left直接移动到字符串里重复字符的右边,再往下循环,只需要一层循环就可以解决问题。

代码:

int lengthOfLongestSubstring_2(char* s) {
    char* left = s;
    char* right = s;
    int res = 0, dummyRes = 0;
    int arr[128] = { 0 };

    while(*right) {
        if(!arr[*right]) {
            arr[*right++] = 1;
            dummyRes += 1;
            res = (res >= dummyRes) ? res : dummyRes;
        } else {
            arr[*left++] = 0;
            dummyRes -= 1;
        }
    }
    return res;
}

int main(int argc, char const *argv[])
{
    char arr[] = "abcabcabc";
    printf("%d\n", lengthOfLongestSubstring_2(arr));
    return 0; 
}

C++ 版

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        int res = 0, dummyRes = 0;
        unsigned left = 0, right = 0;
        set<char> tb;

        while(right < s.size()) {
            if(tb.find(s[right]) == tb.end()) {
                tb.insert(s[right++]);
                dummyRes++;
                res = dummyRes > res ? dummyRes : res;
            }
            else {
                tb.erase(s[left++]);
                dummyRes--;
            }
        }

        return res;
    }
};
Last modification:April 9th, 2020 at 06:45 pm