Leetcode-003-无重复字符的最长子串

Leecode-003-Longest Substring Without Repeating Characters

思路：滑动窗口

题目描述

找出字符串中的无重复子字符串的最大值。

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

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

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

Solution

• 暴力解法时间复杂度太高会达到 O(n^2)，面试如果用的话，那就直接GG了，所以本篇不说这种方法（并且也不需要去用）
• 接下来介绍本题最热门的解法：滑动窗口
  • 定义一个map数据结构存储（k,v），其中key值是字符，value值是字符位置+1,加1表示从字符位置后一个才开始不重复。
  • 定义不重复子串的开始位置为start,结束位置是end
  • 随着end不断向后遍历，会遇到[start,end]区间内有字符相同的情况，此时将字符作为key值，获取它的value值，并更新start,此时新的[start,end]之内就不会存在重复字符。
  • 无论是否更新start,都会更新map和结果ans。

举例子：

需要注意的是下面这个例子（因为hashmap的key不能重复，所以下面的重复key是不完全标准的写法，但是为了使更新value的过程变得明显，所以key这里只是看上去重复而已，实际并没有重复）

"pwwkew"为例

		p	w	w	k	e	w
key		p	w	w	k	e	w	
value	1	2	3	4	5	6
ans		1	2	2	2	3	3
end		0	1	2	3	4	5
start	0	0	2	2	2	3

图解如下：

1. 第一步

2. 第二步

3. 第三步

4. 第四步

5. 第五步

6. 第六步

Java

Solution :

class Solution{
    public int lengthOfLongestSubstring(String s){
        int n = s.length();
        int ans = 0;
        int start = 0;

        // key是字符，value是字符位置+1
        Map<Character, Integer> map = new HashMap<>();
        // 遍历字符串
        for (int end = 0; end < n; end++) {
            // 拿到当前字符
            char curr  = s.charAt(end);
            // 如果当前字符已经出现过，更新窗口start的位置
            if (map.containsKey(curr)){
                start = Math.max(map.get(curr),start);
            }
            // 更新窗口的长度
            ans = Math.max(ans,end - start + 1);
            // 记录end字符
            map.put(s.charAt(end),end + 1);
        }
        return ans;
    }
}

• 时间复杂度：O(n)，遍历一遍字符串的时间开销
• 空间复杂度: O(n) ,额外的hashmap存放元素

测试用例：

public static void main(String[] args) {
    String s = "pwwkew";
    Solution solution = new Solution();
    System.out.println(solution.lengthOfLongestSubstring(s));
}

Python

Solution :字典

• 需要的参数
  • 一个空字典：d (来记录s字符串中所有的位置)
  • 初始位置： start
  • 最大长度： ans
• 步骤：
  • 首先判断当前字符在字典中有没有存在
  • 如果不存在：往字典d中添加当前i,c的记录 同时计算长度为当前索引-初始索引+1
  • 如果之前存在过：那么改变start的位置，也就是把当前start的剔除掉，移动到start的下一位

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        d = {}
        start = 0
        ans = 0
        for i,c in enumerate(s):
            if c in d: #首先判断当前字符在字典中有没有存在
                # 如果之前存在过：那么改变start的位置，也就是把当前start的剔除掉，移动到start的下一位
                start = max(start,d[c] + 1) 
            d[c] = i #如果不存在：往字典d中添加当前i,c的记录  
            ans = max(ans,i-start+1) #同时计算长度为当前索引-初始索引+1
        return ans #遍历完字符串，返回最后的长度

打赏