【图解】三种解法不断优化带你手撕 LeetCode第三号题:无重复字符的最长子串

来源于公众号:苦逼的码农

作者:stul

刷题,AC 不是最终目的,而应该力求最优解,并且总结归纳每个解法的精髓

题目描述

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

示例1:

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

示例2:

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

思路与解法

思路1:暴力法,实际解题中不会使用暴力法,这并不代表我们可以忽略它。

索引从字符串的第一位开始,将后面的字符依次加入到 set 里面。如果 set 里面已经有了该字符,此次循环结束,内循环结束后记录 size。字符串的每一位都用这种方法去计算,得到的最大的 size 即是答案。【图解】三种解法不断优化带你手撕 LeetCode第三号题:无重复字符的最长子串

代码如下(不是Java的也看得懂,我进行了关键语法的注释,下同)

public int lengthOfLongestSubstring(String s) {
        int maxLen = 0;
        for(int i = 0; i < s.length(); i++){
          // 创建一个存放字符的集合
            HashSet<Character> set = new HashSet<>();
            for(int j = i; j < s.length(); j++) {
              // 判断集合是否存在第 j 个字符
                if(set.contains(s.charAt(j)))
                    break;
                set.add(s.charAt(j));
            }
            maxLen = Math.max(maxLen,set.size());
        }
        return maxLen;
    }

(为方便阅读,给出截图)

【图解】三种解法不断优化带你手撕 LeetCode第三号题:无重复字符的最长子串

时间复杂度:O()

空间复杂度:O(m) ,m 为无重复字符的最长子串的长度。

由 思路1 的图可知,i 每次都从下一位开始,其实做了很多无效的计算。思路2将其优化。

思路2:我们设置两根指针(i 和 j )与一个集合set。两个指针之间是一个范围,我们要维护这个范围内不能出现重复的字符。而这个 set 就是是用来判断范围内是否有重复的字符。具体做法如下:i 和 j 开始的时候都指向 字符串首。然后执行下面两个步骤。

  1. 如果 j 指针所指元素未在 set 里面,我们将其 add 进 set 。继续后移 j 。
  2. 如果 j 指针所指元素在 set 里面,我们将 i 指针所指元素从 set 中移除,继续后移 i 。i 会一直往后移,直到 j 的元素不在 set 里面。

我们那示例 2 来详细理解一下。

【图解】三种解法不断优化带你手撕 LeetCode第三号题:无重复字符的最长子串【图解】三种解法不断优化带你手撕 LeetCode第三号题:无重复字符的最长子串【图解】三种解法不断优化带你手撕 LeetCode第三号题:无重复字符的最长子串【图解】三种解法不断优化带你手撕 LeetCode第三号题:无重复字符的最长子串【图解】三种解法不断优化带你手撕 LeetCode第三号题:无重复字符的最长子串【图解】三种解法不断优化带你手撕 LeetCode第三号题:无重复字符的最长子串【图解】三种解法不断优化带你手撕 LeetCode第三号题:无重复字符的最长子串【图解】三种解法不断优化带你手撕 LeetCode第三号题:无重复字符的最长子串【图解】三种解法不断优化带你手撕 LeetCode第三号题:无重复字符的最长子串【图解】三种解法不断优化带你手撕 LeetCode第三号题:无重复字符的最长子串这个过程中,i 与 j 的范围最大的时候,就是我们要求的答案。

HashSet<Character> set = new HashSet<>();
        int i = 0, j = 0, maxLen = 0;
        while (i < s.length() && j < s.length()){
            if (!set.contains(s.charAt(j))){
                set.add(s.charAt(j));
                j++;
                maxLen = Math.max(maxLen,j - i);
            }else {
                set.remove(s.charAt(i));
                i++;
            }
        }
        return maxLen;

代码图片

【图解】三种解法不断优化带你手撕 LeetCode第三号题:无重复字符的最长子串

时间复杂度:O(2n) = O(n) , i 和 j 两个指针。

空间复杂度:O(m) ,m 为无重复字符的最长子串的长度。

思路2 中,我们在遇到重复的字符时,不断在移动 i 指针。这个地方其实可以优化,让 i 指针直接跳到重复元素的下一个位置。

思路3: 让 i 指针直接跳到重复元素的下一个位置。那我们就需要保存每个元素以及它的位置。一个 Value, 一个 Index 。自然会想到 HashMap 。

我们继续拿示例 2 来演示一下。【图解】三种解法不断优化带你手撕 LeetCode第三号题:无重复字符的最长子串【图解】三种解法不断优化带你手撕 LeetCode第三号题:无重复字符的最长子串【图解】三种解法不断优化带你手撕 LeetCode第三号题:无重复字符的最长子串【图解】三种解法不断优化带你手撕 LeetCode第三号题:无重复字符的最长子串【图解】三种解法不断优化带你手撕 LeetCode第三号题:无重复字符的最长子串【图解】三种解法不断优化带你手撕 LeetCode第三号题:无重复字符的最长子串【图解】三种解法不断优化带你手撕 LeetCode第三号题:无重复字符的最长子串【图解】三种解法不断优化带你手撕 LeetCode第三号题:无重复字符的最长子串【图解】三种解法不断优化带你手撕 LeetCode第三号题:无重复字符的最长子串这个地方,能看到优化,但是并不明显。测试用例:pabcwwkew,在纸上用思路 2 和思路 3 画一下这个过程,你会发现思路 3 比思路 2 省略了很多步骤。

public static  int lengthOfLongestSubString4(String s){
  			// 创建一个 key-value 为 字符-下标 相映射的哈希表
        HashMap<Character,Integer> map = new HashMap<>();
        int left = 0, maxLen = 0;
        for(int i = 0; i < s.length(); i++){
          	// 判断是否存在该key
            if(map.containsKey(s.charAt(i))){
               left = Math.max(map.get(s.charAt(i)) + 1,left);
            }
            maxLen = Math.max(maxLen, i - left + 1);
            map.put(s.charAt(i),i);
        }
        return maxLen;
    }

代码图片

【图解】三种解法不断优化带你手撕 LeetCode第三号题:无重复字符的最长子串

时间复杂度: O(n) , 最优解。空间复杂度: O(m) ,m 为无重复字符的最长子串的长度。

在上面所提到的 “范围”,就是一个滑动窗口

其他 leetcode 题目

原文始发于微信公众号(苦逼的码农):【图解】三种解法不断优化带你手撕 LeetCode第三号题:无重复字符的最长子串

本文由 程序员小吴 创作,采用 CC BY 3.0 CN协议 进行许可。 可自由转载、引用,但需署名作者且注明文章出处。如转载至微信公众号,请在先添加作者公众号二维码。
五分钟学算法 » 【图解】三种解法不断优化带你手撕 LeetCode第三号题:无重复字符的最长子串

我还会在以下平台发布内容

GitHub 哔哩哔哩