leetcode刷题记录

leetcode小白每日做题记录

清明期间，断更了几天
习题集：hot100
题目：无重复字符的最长子串长度

做题思路

对于寻找无重复最长子串问题（例如abcabcbb这个字符串，其无重复最长子串为abc，并且长度为3），我首先想到的就是滑动窗口和暴力求解，这个思想在数据结构中也是比较常用的。

滑动窗口的原理是比较容易理解的，接下来通过图示进行说明：

接下来贴一下我的c++代码 ps.其实字符串类的题个人认为用python更加方便

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        int i,j;
        int max = 0,left = 0,right = 0;//left记录左边的指针，right记录右边的指针，max记录字串长
        int len = s.size();
        if(len==0) return 0;//当字符串为空时，无重复最长子串的长度为0
        if(len==1) return 1;//当字符串仅有一个元素时，无重复最长子串的长度为1
        while(right<len){//其他非特殊情况
            for(int j=left;j<right;j++){
                if(s[j]==s[right]){
                    max = (right-left)>max?(right-left):max;
                    left=j+1;
                }
            }
            right++;
            max = (right-left)>max?(right-left):max;//一定不要忘记了最后还可能有无重复子串！若不在最后进行判断则可能会导致当最长无重复子串在末尾位置时，无法更新最长子串长度
        }
        if(left==0&&right==len)
            return len;
        return max;
    }
};

采用滑动窗口的思想无论是时间还是空间上的性能都是很不错滴，记录一下两项突破80%

路漫漫其修远兮