1-无重复字符的最长子串

自己的做法

算法思想

没有什么好的想法。最简单最容易实现的就是暴力求解。

分别从每个字符开始，依次查看该字符之后的字符是否和之前的重复，如果不重复，那么就存入到字符数组中，和之后的字符去比较；如果重复，那就计算出该子串长度，和最长子串长度 变量比较，取较大的一个。直到最后一个字符，

具体做法

使用双指针，p1和p2。最开始同时同时指向字符串，缓存字符数组temp，和数组长度temp_length；先去查看数组中是否有和*p2相等的，如果有，那就算出此段长度，否则将*p2指向的字符存入缓存数组， p2向前移动。

C语言实现

int lengthOfLongestSubstring(char * s){
    if(s == NULL || *s == '\0') {return 0;}

    char *p1 = s;
    char *p2 = s;
    int length = (int) strlen(s);
    //最大子串长度初始设为0
    int maxLength = 0;
    // 缓存数组，存入子串字符
    char temp[length];
    // 数组长度
    int temp_length = 0;

    // 当p1指向'\0'就结束循环
    while (*p1 != '\0'){
        
        // 标志变量，temp数组是否存在p2指向的字符
        int flag = 0;
        for(int j = 0; j < temp_length; j++) {
            //遍历整个temp数组，如果有和*p2相等的，那么设flag为1
            if(*p2 == temp[j]) {
                flag = 1;
                break;
            }
        }
        //如果flag = 1，或者*p2指向了字符串结尾，就将缓存数组长度和最大子串长度比较
        if(flag == 1 || *p2 == '\0') {
            maxLength = maxLength < temp_length ? temp_length : maxLength;
            p1++;
            p2 = p1;
            //将数组长度置为0，即清空数组
            temp_length = 0;
        } else {
            //如果flag = 0，那么就将p2指向的字符串存入缓存，p2指向下一个字符
            temp[temp_length++] = *p2;
            p2++;
        }
    }
    return maxLength;
}

性能分析

时间复杂度是$O(n^2)$，空间复杂度是$O({n})$。

更好的解法

涉及到子串问题的，滑动窗口使用的比较多。

算法思想

当递增地枚举子串起始位置，那么子串结束位置也是递增的。

如果第k个字符是起始位置，第k + h 个字符是结束位置，那么当选择第k + 1个字符作为起始位置时，显然从k + 1到k + h的字符是不重复的，然后可以从 k + h开始继续向右比较，直到出现了重复字符。

具体做法

• 使用双指针，并使用一个集合来存入当前滑动窗口内的字符。
• 在循环体内，先判断集合中是否存在右指针的下一个位置(即*(p + 1) )指向的字符，如果存在；那就结束循环，并计算此时子串长度；如果不存在，则右指针向右滑动一个位置，继续该操作
• 在上一步结束循环后，左指针应向右移动一个位置，同时从集合中删除左指针先前指向的字符，继续循环
• 直到遍历完整个字符串，循环结束

C++实现

class Solution {

public:
    int lengthOfLongestSubstring(string s) {
        unordered_set<char> chars;
        int size = s.size();
        int right = -1, max_length = 0;
        for(int i = 0; i < size; i++) {
            if(i != 0) {
                chars.erase(s[i - 1]);
            }
            while (right < size - 1 && !chars.count(s[right + 1])) {
                chars.insert(s[right + 1]);
                right++;
            }
            max_length = max(max_length, right - i + 1);
        }
        return max_length;

    }
};

性能分析

• 时间复杂度：$O(N)$，N为字符串长度。