算法:无重复字符的最长子串
算法 About 1,539 words题目
给定一个字符串,请你找出其中不含有重复字符的最长子串的长度。
示例一
输入: s = "abcabcbb"
输出: 3
解释: 因为无重复字符的最长子串是 "abc",所以其长度为 3。
示例二
输入: s = "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b",所以其长度为 1。
示例三
输入: s = "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke",所以其长度为 3。
请注意,你的答案必须是 子串 的长度,"pwke" 是一个子序列,不是子串。
示例四
输入: s = ""
输出: 0
提示
0 <= s.length <= 5 * 10^4
s
由英文字母、数字、符号和空格组成
思路
创建数组记录字符出现过的位置。定义start
指针记录最长字串开始的索引,当符号出现过时,start
指针指向上一次出现的位置的下一位,但要注意判断start
指针只能一直往后移,如果符号出现的索引位置比start
小,则start
位置不变。
实现
public static int lengthOfLongestSubstring(String s) {
// 记录字符上一次出现的位置
// 英文字母、数字、符号和空格,不考虑 & 等中文符号。
int[] last = new int[128];
for (int i = 0; i < 128; i++) {
last[i] = -1;
}
int longestCount = 0;
int start = 0; // 开始位置指针
for (int i = 0; i < s.length(); i++) {
int charAscii = s.charAt(i);
int index = last[charAscii];// 字符上一次出现的位置,没出现过就是-1
if (index != -1) {// 如果出现过,开始位置指针指向上一次出现的位置的下一位
// 如:dvdf,第一次d出现在第0位,所以最长子串开始计算的索引就是0,但当第二个d出现了,所以有重复了,最长子串的计算计算的索引也要往后移一位,从v开始计算。
// 如:abba,第一次a出现在第0位,但当第二个d出现时,索引往后移一位就要比较原先记录的start即b的下一位索引大还是a的下一位索引大。
// start = index + 1; // 要防止 abba 情况,故 index + 1 与之前记录的 start 比大小
start = Math.max(start, index + 1);
}
longestCount = Math.max(longestCount, i - start + 1);
last[charAscii] = i;
}
return longestCount;
}
LeetCode 原题地址
https://leetcode-cn.com/problems/longest-substring-without-repeating-characters
Views: 1,494 · Posted: 2021-02-24
————        END        ————
Give me a Star, Thanks:)
https://github.com/fendoudebb/LiteNote扫描下方二维码关注公众号和小程序↓↓↓
Loading...