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

╰半夏微凉° 2023-03-13 05:15 3阅读 0赞

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

# 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 时间复杂度 ###

![在这里插入图片描述][20200511115502659.png]  
O(N)

### 2.2.4 空间复杂度 ###

`O(C)`

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

[20200511115502659.png]: /images/20230312/05cf20184a2c47b18cc0c160fda65c19.png