LeetCode 第三题 (Longest Substring Without Repeating Characters) 三部曲之二：编码实现

作者：程序员欣宸

2022 年 8 月 03 日
本文字数：1038 字
阅读完需：约 3 分钟

LeetCode第三题(Longest Substring Without Repeating Characters)三部曲之二：编码实现

欢迎访问我的 GitHub

这里分类和汇总了欣宸的全部原创(含配套源码)：https://github.com/zq2599/blog_demos

本文是《LeetCode 第三题(Longest Substring Without Repeating Characters)三部曲》的第二篇，前一篇文章已经列出了完整的解题思路，今天来将此思路转化为具体的 Java 代码；

关键变量

编码之前先确定几个关键变量：
当前窗口中的元素都是不重复的，适合用一个 HashSet 来保存；
max 变量记录最长子串的长度；
left 表示窗口左侧相对整个字符串的位置，right 表示窗口右侧相对整个字符串的位置，如下图：

代码实现

以下是代码，关键位置都有详细注释：

public class Solution1 {
    public int lengthOfLongestSubstring(String s) {        //窗口的起始位置,窗口的结束为止,最长记录        int left = 0, right = 0, max = 0;
        //表示窗口内有哪些值        Set<Character> set = new HashSet<>();
        while (right < s.length()) {            //例如"abcdc"，窗口内是"abcd"，此时right等于[4],            //发现窗口内有array[right]的值，就缩减窗口左边，            //缩到窗内没有array[right]的值为止，            //当left一路变大，直到left=3的时候，窗口内已经没有array[right]的值了            if (set.contains(s.charAt(right))) {                //假如窗口内是"abc"，当前是"c"，那么下面的代码只会将"a"删除,left加一，再次循环                //而新一次循环依旧发现"c"还在set中，就再把"b"删除，left再加一...                set.remove(s.charAt(left++));            } else {                //窗口内没有array[right]的时候，就把array[right]的值放入set中，表示当前窗口内有哪些值                set.add(s.charAt(right++));
                if ((right - left) > max) {                    max = right - left;                }            }        }
        return max;    }
    public static void main(String[] args) {        System.out.println(new Solution1().lengthOfLongestSubstring("abcabcbb"));    }}

复制代码

上述代码的关键是 set.remove(s.charAt(left++))，配合着外面的 while 循环，"left++"表示将窗口向右移动一个元素，并且将窗口中最左侧的元素从 set 中删除；
上述代码在 LeetCode 上提交成功，不过运行时间超过 40ms，成绩并不理想，接下来的文章我们一起来做优化提升速度；