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

无重复字符的最长字串

  有人白天相爱，有人夜里看海，有人LeetCode的第一题都做不出来。记录一下在力扣上看到的，让人耳目一新的解法。

题目描述.

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

示例 1:输入: s = "abcabcbb"输出: 3 解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。

示例 2:输入: s = "bbbbb"输出: 1解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。

示例 3:输入: s = "pwwkew"输出: 3解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。

示例 4:输入: s = ""输出: 0

提示：0 <= s.length <= 5 * 104s 由英文字母、数字、符号和空格组成

  以上为LeetCode的第三题。在评论区看到一位叫“南星”的大佬，他给出了这样一段代码。(大佬原本用java实现的，我改成了C#版本。由于C#没有string.CharAt()方法，我自己写了一个扩展方法。)

public static int LengthOfLongestSubstring(string s)        {
               //记录字符上一次出现的位置            int[] last = new int[128];            for (int i = 0; i < record.Length; i++)            {
                   record[i] = -1;            }            int n = s.Length;            int res = 0;            int start = 0;//窗口开始的位置            for (int i = 0; i < n; i++)            {
                   int index = s.CharAt(i);                start = Math.Max(start, last[index]+1);                res = Math.Max(res, i - start + 1);                last[index] = i;            }            return res;        }

/// 
    /// CharAt扩展方法    /// 
    public static class CharAtExtend    {
           public static char CharAt(this string s, int index)        {
               return s.Substring(index, 1)[0];        }    }

  第一遍从头读到尾的时候人有点懵，完全没有领会到这段代码的意图（我相信很多人和我一样）。当我第二遍细细品读的时候，好家伙，醍醐灌顶。我举个栗子，解释一下这段代码。

  首先声明了一个长度为128的整形数组，用作记录每个字符在字符串中出现的位置下标。所有元素初始化为-1，当有对应元素出现时，记录元素在字符串中的位置。

  128对应着ASCII码的128个字符。ASCII码，是使用7 位二进制数（剩下的1位二进制为0）来表示所有的大写和小写字母，数字0 到9、标点符号，以及在美式英语中使用的特殊控制字符。（忘记ASCII码的同学可以百度看看，这里不做太多复述）

  声明一个start记录不重复字符串开始的位置，res记录最大长度。然后遍历我们想要查找的字符串，以“abacd”举例，开始遍历。（字符“abcd”在ASCII表中的位置为“97、98、99、100”）

  i=0时指向字符串中的"a",我们查看数组中Last[97]的值+1=0，说明该字符是第一次出现，并没有出现重复，start仍从第0位开始计数，此时不重复字串res的值为1，last中记录位置0。( 注：res为最长串的值。i - start +1是当前在字串中的位置减去记录开始的位置，是当前记录的不重复字串的长度。如果该值大于 res 则赋值，小于res 则res的值不变。)

  i=1时指向字符串中的"b",我们查看数组中Last[98]的值+1=0，说明该字符是第一次出现，并没有出现重复，start仍从第0位开始计数，此时不重复字串res的值为2，last中记录位置1。

  i=2时指向字符串中的"a"，我们查看数组中Last[97]的值为0，说明该字符已经出现过了，并且上一次出现位置是0。这是要略过这个重复的字符“a”，start从第Last[97]+1位（也就是b的位置）开始计数，此时不重复字串res的值为2，last中记录位置2。

  i=3时指向字符串中的"c",我们查看数组中Last[99]的值+1=0，说明该字符是第一次出现，并没有出现重复，start仍从第1位开始计数，此时不重复字串res的值为3，last中记录位置3。   i=4时指向字符串中的"d",我们查看数组中Last[100]的值+1=0，说明该字符是第一次出现，并没有出现重复，start仍从第1位开始计数，此时不重复字串res的值为4，last中记录位置4。

  字符串遍历结束，最长串为从1开始4结束的 “bacd” ,最长串的大小值为4。

转载地址：https://blog.csdn.net/m0_56500170/article/details/115266225 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！