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()) {
 //例如&quot;abcdc&quot;，窗口内是&quot;abcd&quot;，此时right等于[4],
 //发现窗口内有array[right]的值，就缩减窗口左边，
 //缩到窗内没有array[right]的值为止，
 //当left一路变大，直到left=3的时候，窗口内已经没有array[right]的值了
 if (set.contains(s.charAt(right))) {
 //假如窗口内是&quot;abc&quot;，当前是&quot;c&quot;，那么下面的代码只会将&quot;a&quot;删除,left加一，再次循环
 //而新一次循环依旧发现&quot;c&quot;还在set中，就再把&quot;b&quot;删除，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(&quot;abcabcbb&quot;));
 }
}


• 上述代码的关键是
  set.remove(s.charAt(left++))
  ，配合着外面的while循环，"left++"表示将窗口向右移动一个元素，并且将窗口中最左侧的元素从set中删除；

• 上述代码在LeetCode上提交成功，不过运行时间超过40ms，成绩并不理想，接下来的文章我们一起来做优化提升速度；

欢迎关注InfoQ：程序员欣宸

学习路上，你不孤单，欣宸原创一路相伴...