算法:无重复字符的最长子串

算法 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

扫描下方二维码关注公众号和小程序↓↓↓

扫描下方二维码关注公众号和小程序↓↓↓


Today On History
Browsing Refresh