3、无重复字符的最长子串（java） --- Leetcode日常刷题

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

class Solution {
    public int lengthOfLongestSubstring(String s) {
        //使用队列
        //定义一个变量，存放要返回的最大长度值，默认值为0;
        int maxLength = 0;
        Queue queue = new LinkedList<>();
        for (int i = 0; i < s.length(); i++) {
            //判断当前队列中是否存在此字符，存在则将此字符及之前的移除（因为先进先出的原则，此元素A之前的元素会比元素A先出队）
            while (queue.contains(s.charAt(i)))
                queue.poll();
            //将元素放入到队列中（进队）
            queue.offer(s.charAt(i));
            //将queue的长度和maxLength的值进行对比，取最大值
            maxLength = Math.max(maxLength,queue.size());
        }
        
        return maxLength;

    }
}

结果：

class Solution {
    public int lengthOfLongestSubstring(String s) {
         //使用Hashset
        int maxLength = 0;
        //需要一个窗口，用来滑动时存放数据
        Set windows = new HashSet<>();
        //需要为窗口的左右两边设置初始值,可以当作HashSet左右两端的坐标
        int left = 0;
        int right = 0;

        while(right < s.length()){
            //从左边移除重复的字符
            while (windows.contains(s.charAt(right)))
                windows.remove(s.charAt(left++));
            //将当前字符添加到窗口中
            windows.add(s.charAt(right++));
            //比较当前windows中的元素个数与当前最大不重复字串长度的大小，maxLength取最大值
            maxLength = Math.max(maxLength,windows.size());
        }
        return maxLength;
    }
}

class Solution {
    public int lengthOfLongestSubstring(String s) {
         //使用数组
        int maxLength = 0;
        int[] dict = new int[128];
        //初始化数组
        Arrays.fill(dict,-1);
        int left = 0;
        for (int right = 0; right < s.length() ; right++) {
            //确保左端的值在碰到重复的值后会向右移动
            left = Math.max(left,dict[s.charAt(right)]+1);
            dict[s.charAt(right)] = right;
            maxLength = Math.max(maxLength,right-left+1);
        }
        return maxLength;
    }
}

如下官网中的两张视频截图帮助理解数组方法的原理。

• 获取字符串的第i个字符：使用chartAt（）

    public char charAt(int index) {
        if ((index < 0) || (index >= value.length)) {
            throw new StringIndexOutOfBoundsException(index);
        }
        return value[index];
    }

• ++i和i++的区别

1、效果上：一样。均是 i = i + 1 ;
2、当成运算符
i = 1 ;
a = i++ ;  //先赋值，后自增。即a = 1，i = 2;
a = ++i ; //先自增，后赋值。即 a = 2，i = 2;

知乎中的详细讲解

• 队列的进队和出队

//创建了一个队列
Queue queue = new LinkedList<>();
//出队方法
queue.poll();
//进队方法
queue.offer(s.charAt(i);

//队列，继承了集合
public interface Queue extends Collection {

    
    E poll();


    
    boolean offer(E e);
}