@[toc]

无重复字符的最长子串

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

示例1:

输入: s = "abcabcbb"
输出: 3 
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。

示例2:

输入: s = "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。

示例3:

输入: s = "pwwkew" 输出: 3 解释: 因为无重复字符的最长子串之一是 "wke"，所以其长度为 3。请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。

提示:

• 0 <= s.length <= 5 * 104

• s 由英文字母、数字、符号和空格组成

coding before

圈主也是刚刚刷题的拉, 刷题前, 因为自己也是第一次做这个题目, 所以大致浏览了一下具体思路,找了官方的题解看了一下。然后决定代码实现,落地一下,看自己是否有理解题解所说。

看了一圈, 发现做这种题目大多是采用滑动窗口来做的。

基于该题刷完个人对于滑动窗口的一个浅浅的理解:

• 使用两个指针(a, b)来定义窗口的位置

• 指针a往后面滑, 滑的同时需要做如下三件事情,

  • 记录滑动过的元素值

  • 判断当前滑动的元素是否是重复元素,

    • 不是重复元素则指针a继续往后面滑动,

    • 是重复元素则指针a保持不动,指针b需要先把自身从容器中移除再继续滑动。

  • 记录当前滑动过的最大值

coding

第一次尝试:

public int lengthOfLongestSubstring(String s) {
        int length = s.length();
        int longestSubstring = 0;
        if (length == 0) return longestSubstring;
        int left = 0, right = 0;
 &nbsp; &nbsp; &nbsp; &nbsp;Set<Character> set = new HashSet<>(length);
 &nbsp; &nbsp; &nbsp; &nbsp;for (int i = 0; i < length; i++) {
 &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;++right;
 &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;if (!set.add(s.charAt(i))) {
 &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;++left;
 &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;  }
 &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;longestSubstring = Math.max(longestSubstring, (right - left));
 &nbsp; &nbsp; &nbsp;  }
 &nbsp; &nbsp; &nbsp; &nbsp;return longestSubstring;
 &nbsp;  }

ps: "pwwkew" 用例不过

第二次尝试,没理解精髓,又错了

public int lengthOfLongestSubstring1(String s) {
        int length = s.length();
        int longestSubstring = 0;
        if (length == 0) return longestSubstring;
        int left = 0, right = 0;
        char x = 0;
 &nbsp; &nbsp; &nbsp; &nbsp;Set<Character> set = new HashSet<>(length);
 &nbsp; &nbsp; &nbsp; &nbsp;for (int i = 0; i < length; i++) {
 &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;++right;
 &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;char e = s.charAt(i);
 &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;if (!set.add(e)) {
 &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;left = (x == e) ? i : ++left;
 &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;  }
 &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;x = e;
 &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;longestSubstring = Math.max(longestSubstring, (right - left));
 &nbsp; &nbsp; &nbsp;  }
 &nbsp; &nbsp; &nbsp; &nbsp;return longestSubstring;
 &nbsp;  }

ps: "ckilbkd" 用例不过

看了题解,第三次尝试,成功啦

public int lengthOfLongestSubstring2(String s) {
        int longestSubstring = 0;
        int length = s.length();
        if (length == 0) return longestSubstring;
        // 哈希集合，记录每个字符是否出现过
 &nbsp; &nbsp; &nbsp; &nbsp;Set<Character> set = new HashSet<Character>();
​
 &nbsp; &nbsp; &nbsp; &nbsp;// 右指针，初始值为 0，相当于我们在字符串的左边界的左侧，还没有开始移动
 &nbsp; &nbsp; &nbsp; &nbsp;int right = 0;
 &nbsp; &nbsp; &nbsp; &nbsp;for (int i = 0; i < length; ++i) {
 &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;if (i != 0) {
 &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;// 左指针向右移动一格，移除一个字符
 &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;set.remove(s.charAt(i - 1));
 &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;  }
 &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;while (right &nbsp;< length && set.add(s.charAt(right))) {
 &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;// 不断地移动右指针
 &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;++right;
 &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;  }
 &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;// 第 i 到 right 个字符是一个极长的无重复字符子串
 &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;longestSubstring = Math.max(longestSubstring, right - i);
 &nbsp; &nbsp; &nbsp;  }
 &nbsp; &nbsp; &nbsp; &nbsp;return longestSubstring;
 &nbsp;  }

内存消耗超过23% , 执行用时超过60%

大佬指点,又学到东西啦

    public int lengthOfLongestSubstring3(String s) {
        boolean[] flag = new boolean[128];
        int ret = 0;
        int right = 0;
        int length = s.length();
 &nbsp; &nbsp; &nbsp; &nbsp;for (int left = 0; left < length;left++) {
 &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;while (right < s.length() && !flag[s.charAt(right)]) {
 &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;flag[s.charAt(right)] = true;
 &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;right++;
 &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;  }
 &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;ret = Math.max(ret, right - left);
 &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;flag[s.charAt(left)] = false;
 &nbsp; &nbsp; &nbsp;  }
 &nbsp; &nbsp; &nbsp; &nbsp;return ret;
 &nbsp;  }

内存消耗超过68% 执行用时超过93%

coding end

小伙伴们如果有优质的解法或者相关联的题目, 欢迎留言评论(ps: 格式为 力扣题目编号 + 执行用时 + 内存消耗), 大家一起互相学习,共同进步嗷。