leetcode:Longest Substring Without Repeating Characters解题报告

    xiaoxiao2021-03-25  69

    Longest Substring Without Repeating Characters

    1、原题

    Given a string, find the length of the longest substring without repeating characters.

    2、题目解析及分析

    题目一目了然,很简单,让我们一遍找到一个字符串的最小子串。 首先,这道题的思路很简单,可以在遍历的时候将已经出现的字符存在数组中进行标记。在遇到下一个字母时要去查找相应的位置有没有标记,然后进一步操作。具体逻辑思路如下: 1、初始化一个256的数组用于标记字符的出现情况。一个起始标志start。 2、遍历数组,若数组未标记过或标记下标小于起始位置start,将该数组标记为现在的下标位置。若数组已标记且标记的下标大于起始位置start,使用当前位置减去起始位置与最大值进行比较,然后将起始位置置为当前位置。 3、结束后再进行一次长度判断。

    3、实现与注意点

    public class Solution { public int lengthOfLongestSubstring(String s) { int maxLength = 0, start1 = 0; int[] ASCIIlist = new int[256]; for (int i = 0; i < 256; i++) { ASCIIlist[i] = -1; } for (int i = 0; i < s.length(); i++) { if (ASCIIlist[(int)s.charAt(i)] >= start1) { maxLength = (maxLength > (i - start1) ? maxLength : (i - start1)); start1 = ASCIIlist[(int)s.charAt(i)] + 1; } ASCIIlist[(int)s.charAt(i)] = i; } maxLength = (maxLength > (s.length() - start1) ? maxLength : (s.length() - start1)); return maxLength; } }

    注意:由于起始位置为1,所以将数组初始化为了-1.

    转载请注明原文地址: https://ju.6miu.com/read-35536.html

    最新回复(0)