本文共 1742 字，大约阅读时间需要 5 分钟。

算法-水位-无重复字符的最长子串

1 概述

1.1 题目出处

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

1.2 题目描述

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

示例 1:

输入: “abcabcbb”

输出: 3 解释: 因为无重复字符的最长子串是 “abc”，所以其长度为 3。 示例 2:

输入: “bbbbb”

输出: 1 解释: 因为无重复字符的最长子串是 “b”，所以其长度为 1。 示例 3:

输入: “pwwkew”

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

2 题解

2.1 水位

2.2.1 解题思路

思路是关注最近的两个相同字符间距离，同时增加水位限制，水位始终为0或相同字符较旧那个位置的下一个位置。

水位指向当前首个不重复数字位置，用来限制计算重复元素的最小位置，不能低于水位去找重复元素来计算路径长度，因为水位所在的位置之前已经有其他重复元素了。

比如abca，初始为0，直到第二个a时水位更新为前一个a的下一个位置即1

再比如 kacbak 第一次遇到重复元素a时，将水位置为 1 + 1 = 2 第二次，又遇到重复元素k，此时因为上次重复的k的位置0在数位2之下，表示旧k位置和水位之间有其他重复元素，这里就是a 所以不能直接以 第二个k的位置 5 - 第一个k的位置的下一个位置 1 + 1 这样计算长度，因为存在重复元素a！

同时本算法用128位的int数组代替了HashMap，速度再次提高

取128的原因是ascii码一共128个。也可以设为256，因为char为8bit，即针最多2^8-1 个字符

2.2.2 代码

class Solution {
       public int lengthOfLongestSubstring(String s) {
           int result = 0;        if(s == null || s.length() == 0){
               return result;        }        int watermark = 0;        int[] positions = new int[128];         char[] cs = s.toCharArray();        int tmp = 0;        for(int i = 0; i < cs.length; i++){
               char c = cs[i];            int old = positions[c] - 1;            if(old == -1){
                   tmp += 1;            }else{
                   if(old < watermark){
                      tmp += 1;                 }else{
                      watermark = old + 1;                   result = Math.max(tmp, result);                   tmp = i - watermark + 1;                }            }            positions[c] = i + 1;        }        return Math.max(result, tmp);    }}

2.2.3 时间复杂度

O(N)

2.2.4 空间复杂度

O(C)

• C为字符集大小
  也可以用HashMap代替int数组，只不过效率会低一些，因为可能会存在扩容、Hash冲突、链表变红黑树等操作。

转载地址：http://zmpkb.baihongyu.com/