leetcode 3 无重复字符最长串

vastjoy / 2024-08-31 / 原文

leetcode 3 无重复字符最长串

思路

使用滑动窗口，建两个整型变量lp和rp，分别代表左边界指针和右边界指针，整型temp储存当前字串长度，整形max储存当前最长长度，然后从左往右遍历字符串。

解题过程

先将字符串toCharArray转成字符数组m，建一个哈希集合，储存当前已经用过的字符，然后写一个while循环，在循环中主要进行两步操作： 1.如果右边界字符在哈希集合中已经存在，说明这个左边界已经讨论结束，lp++，然后将m[lp]从集合中移除掉，temp--。 2.如果右边界字符在哈希集合中不存在，那么将m[rp]加入集合，temp++，max=Math.max(max,temp)。同时需要注意进行while循环需要一定的条件，即字符串不为空（如果是空字符串chars.add(m[0])会报错）。并且这里判断字符串不为空要用isEmpty()函数，而不能用length>0（如果字符串里全是空格占位符，那length也是0）

复杂度

时间复杂度: O(n)

分析：左右边界都在动，且while循环边界条件是右边界到头。那么最坏情况下，右边界一直动，并且左边界一直跟着动到右边界左侧与其相邻，且HashSet的contains，remove，add复杂度都是o(1)，因此总复杂度为O(2n)*O(1)，即复杂度为O(n)。

class Solution {
       public int lengthOfLongestSubstring(String s) {
        int lp=0,rp=1,max=1,temp=1;
        HashSet<Character> chars = new HashSet<Character>();
        char[] m=s.toCharArray();
        int len=m.length;
        if(s.isEmpty()==false){
            chars.add(m[0]);
            while (rp<len){
                if(chars.contains(m[rp])){
                    chars.remove(m[lp]);
                    lp++;
                    temp--;
                }
                else {
                    chars.add(m[rp]);
                    rp++;
                    temp++;
                    max=Math.max(max,temp);
                }
            }
            return max;
        }
        else return 0;
    }
}