无重复字符的最长子串【三种解法】--LeetCode

╰半橙微兮° 2022-03-09 12:56 109阅读 0赞

## 题目描述 ##

给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。

输入: "abcabcbb"
    输出: 3 
    解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。

输入: "bbbbb"
    输出: 1
    解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。

输入: "pwwkew"
    输出: 3
    解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
         请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。

## 算法简析 ##

*  通过i,j构建滑动窗口。（因为只能是连续的子串）达到O(n)。
 *  每一步需要找到，添加对应的一个点，是否已经在原表中存在了。在cpp上，我这里用了一个队列的出入队列来进行模拟。同时构建一个hash表来用O(1)的复杂度来进行定位。

改进思路：队列在这个步骤中似乎用处不大。直接用游标i来记录左窗口的数值即可。

## 原版代码 ##

#include <queue>
    class Solution { 
    public:
        int lengthOfLongestSubstring(string s) { 
            int ans = 0, i = 0, j = 0, max_=0, n=s.size();
            
            for(i = 0; i < s.size(); ++i) { 
                max_ = (max_ > s[i]) ? max_ : s[i];
            }
            
            bool * b_ptr = new bool[max_+1];
            for(i = 0; i <= max_; ++i) { b_ptr[i] = false;}
            i = 0, j = 0;
            int tmp;
            queue<int> q;
            while (i < n && j < n) { 
                if(!b_ptr[s[j]]) { 
                    b_ptr[s[j]]=true;
                    q.push(s[j]);
                    j++;
                    ans = (ans > j - i) ? ans : j - i;
                } else { 
                    tmp = q.front();
                    q.pop();
                    i++;
                    b_ptr[tmp]=false;
                }
            }
            delete[] b_ptr;
            return ans;
        }
    };

## 改进版代码 ##

*  将队列去掉，直接用i来定位之前的序列

再改进思路：数组规模过大。初始化时间或称为最大的下限。

class Solution { 
    public:
        int lengthOfLongestSubstring(string s) { 
            int ans = 0, i = 0, j = 0, max_=0, n=s.size();
            
            for(i = 0; i < s.size(); ++i) { 
                max_ = (max_ > s[i]) ? max_ : s[i];
            }
            
            bool * b_ptr = new bool[max_+1];
            for(i = 0; i <= max_; ++i) { b_ptr[i] = false;}
            i = 0, j = 0;
            int tmp;
            while (i < n && j < n) { 
                if(!b_ptr[s[j]]) { 
                    b_ptr[s[j]]=true;
                    j++;
                    ans = (ans > j - i) ? ans : j - i;
                } else { 
                    tmp = s[i++];
                    b_ptr[tmp]=false;
                }
            }
            delete[] b_ptr;
            return ans;
        }
    };

## 再改进 ##

*  将数组的规模变得更小
 *  但是添加了每次都要进行一次加法的运算，这样很影响时间效率。

根据估算，ascii码的长度其实有限，所以空间大小不会有太的的变化，但是，时间上的增加却是不可原谅的。

class Solution { 
    public:
        int lengthOfLongestSubstring(string s) { 
            if (s.size() == 0) return 0;
            int ans = 0, i = 0, j = 0, max_=0, n=s.size(), min_;
            
            for(i = 0; i < s.size(); ++i) { 
                max_ = (max_ > s[i]) ? max_ : s[i];
                min_ = (min_ < s[i]) ? min_ : s[i];
            }
            
            bool * b_ptr = new bool[max_ - min_ + 1];
            for(i = 0; i <= max_ - min_; ++i) { b_ptr[i] = false;}
            i = 0, j = 0;
            int tmp;
            while (i < n && j < n) { 
                if(!b_ptr[s[j] - min_]) { 
                    b_ptr[s[j] - min_]=true;
                    j++;
                    ans = (ans > j - i) ? ans : j - i;
                } else { 
                    tmp = s[i++];
                    b_ptr[tmp - min_]=false;
                }
            }
            delete[] b_ptr;
            return ans;
        }
    };