【Leetcode】3. Longest Substring Without Repeating Characters

题目地址：

https://leetcode.com/problems/longest-substring-without-repeating-characters/

题目大意是，给定一个字符串，求其中的一个最长子串不含重复字母，返回其长度。

法1：双指针 + 维护每个字符出现的最后位置。用一个map保存快指针遍历到$j$的时候$s[0,...,j]$所有字母最后出现的位置，快指针从$0$向后遍历，如果遇到了map里未保存的字符，说明遇到了新字符，子串可以扩展，更新答案并且将该字母和它的位置存入map；否则，说明遇到了重复字符，如果该字符出现在慢指针之后，那么就将慢指针向后移动到该重复字母之前出现的位置+1（也就是map里存储的该字符出现的位置+1），否则不更新慢指针（因为慢指针不能回退，否则就把重复字符加进$s[i,...,j]$了）。这样就仍然保证了$[i,j]$里没有重复元素。

import java.util.HashMap;
import java.util.Map;

public Solution {
	public int lengthOfLongestSubstring(String s) {
    	int res = 0;
    	// 用一个map来标记每个字母最后一次出现的下标
    	Map<Character, Integer> map = new HashMap<>();
    	for (int i = 0, j = 0; j < s.length(); j++) {
    		// 如果快指针所在位置的字符出现过，那就将慢指针挪到其最后一次出现的位置后一位
        	if (map.containsKey(s.charAt(j))) {
            	i = Math.max(map.get(s.charAt(j)) + 1, i);
        	}
        	
        	res = Math.max(res, j - i + 1);
        	// 更新一下s[j]出现的最新位置
        	map.put(s.charAt(j), j);
    	}
    	
    	return res;
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

时空复杂度$O(n)$。

算法正确性证明：
只需要证明每次循环结束的时候：
1、$s[i,...,j]$中无重复字母
2、$res$已经保存了$s[0,...,j]$中最长无重复子串的长度
3、$map$里保存了$s[0,...,j]$中所有字母最后出现的位置。

数学归纳法：当$j=0$时，$res=1,map=\{(s[0],0)\}$，显然成立。假设当$j=k$时成立，在$j=k+1$的循环开始时，如果map.containsKey(s.charAt(j))为真，说明$s[0,...,k]$中出现过$s[j]$，如果出现的位置在$i$之前，那么$s[i,...,k+1]$仍然没有重复元素，这时以$s[k+1]$结尾的最长重复子串是$s[i,...,k+1]$；如果出现的位置在$i$或者$i$之后，比如在$l$，那么以$s[k+1]$结尾的最长重复子串是$s[l+1,...,k+1]$。所以经过if判断后，$s[i,...,j]$就成为以$s[j]$结尾的最长无重复字符子串了，循环结尾时res和map得到了更新，第2和第3条性质显然保持。由数学归纳法，遍历结束后，res里保存了正确答案。证明完毕。

法2：双指针 + 维护区间内字符出现次数。用快慢指针维护一个中间没有重复字符的区间，并用一个count数组来维护区间内字符出现的次数（当做哈希表来用）。如果快指针走到一个出现次数大于$1$的字符，则右移慢指针，直到这个字符出现次数等于$1$为止。每次维护完区间的字符不重复这个属性之后，就更新答案。代码如下：

public class Solution {
    public int lengthOfLongestSubstring(String s) {
        int res = 0;
        int[] count = new int[128];
    
        for (int j = 0, i = 0; i < s.length(); i++) {
            count[s.charAt(i)]++;
            while (count[s.charAt(i)] > 1) {
                count[s.charAt(j)]--;
                j++;
            }
            
            res = Math.max(res, i - j + 1);
        }
        
        return res;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

时间复杂度$O(n)$，空间$O(1)$。

C++：

class Solution {
 public:
  int lengthOfLongestSubstring(string s) {
    unordered_map<char, int> mp;
    int res = 0;
    for (int i = 0, j = 0; i < s.size(); i++) {
      mp[s[i]]++;
      while (mp[s[i]] > 1) mp[s[j++]]--;
      res = max(res, i - j + 1);
    }

    return res;
  }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14

时空复杂度一样。