当前位置：网站首页>力扣第三题——无重复字符的最长子串

力扣第三题——无重复字符的最长子串

2022-07-19 18:22:00 【InfoQ】

前言

日更停了，每周二的刷题不能停！

这道题，也是中等难度，然后我也是一顿操作猛如虎，提交超过百分五~~。我特别想知道都谁被我超过了

（实际是超过了7%）

这里我想先多说一句，做这类算法类的题，思路是千千万的，但如果之前搞算法搞的少，可能短时间内跳不出固有的那套做业务的思路，题目多拐几个弯，可能就自己把自己卡死了。

实际我感觉，做算法，就应该抛掉经验包袱，真的动动脑筋，动笔在纸上画一画，写一写，可能会有思路出来。而且刷算法题真的可以让我们日渐固化的业务思维变得更加灵活。（只是个人感觉，其实我也菜的一批，但每次解出来题，不管超过百分几吧，能做出来我就很开心了）

题目分析

先奉上

试题链接

然后这里也列一下具体题目

无重复字符的最长子串
给定一个字符串 s ，请你找出其中不含有重复字符的最长子串的长度。
示例 1:
输入: s = "abcabcbb"
输出: 3
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。
示例 2:
输入: s = "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。
示例 3:
输入: s = "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
请注意，你的答案必须是子串的长度，"pwke" 是一个子序列，不是子串。

这个题虽然内容不长，但官方给了一个中等的标签

可能是因为题目简单,我就还是凭着之前做项目的经验，就开始解题了。

猛如虎的解法

看下我这一顿的操作是咋弄的

public static int LengthOfLongestSubstring2(string? s)
{
 if(string.IsNullOrEmpty(s))
 {
 return 0;
 }
 if(s.Length==1)
 {
 return 1;
 }
 char[] chars = s.ToCharArray();
 Hashtable hashtable = new Hashtable();
 int index = 0;
 int maxLen = chars.Length;
 List<int> list = new List<int>();
 while (index < maxLen)
 { 
 hashtable.Clear();
 for (int i = index; i < chars.Length; i++)
 {
 if (hashtable.ContainsKey(chars[i]))
 {
 list.Add(hashtable.Count);
 index++; 
 break;
 }
 hashtable.Add(chars[i], i);
 if (i == chars.Length - 1)
 {
 index++;
 list.Add(hashtable.Count);
 }
 }

 }
 list.Sort((x, y) => -x.CompareTo(y));
 return list[0];
}

别看操作辣眼，实际是可以通过官方所有用例的！

思路如下

先排除掉特殊情况，空输入和单字符

常规字符，自然划分

在指定循环范围内（其实也是一步步缩短循环次数），利用hashtable的特性，把每个字节和索引值存入哈希表

每次循环都把哈希表的值计入到List里

循环结束后，整理List，按大小倒序排序，取第一个值就是题目要求的那个值。

这么写，我感觉是非常典型的业务写法，杂糅了哈希表，列表两个数据结构，显然会消耗更多的内存，也就是空间复杂度。另外，多次遍历，也会造成时间复杂度提高。所以这是一个通过经验，超着解题思路的方向，碰撞出来的一个解法，显然不能当成标准，规范的解法来做！

标准的解法

解法的分析我就不多说了，直接奉上

传送门

以及C#的解法，这个官方没有标准答案，我是根据Java的写法稍微调整了一下改成了C#的写法

public static int LengthOfLongestSubstring(string? s)
{
 // 哈希集合，记录每个字符是否出现过
 HashSet<Char> occ = new HashSet<Char>();
 int n = string.IsNullOrEmpty(s) ? 0 : s.Length;
 // 右指针，初始值为 -1，相当于我们在字符串的左边界的左侧，还没有开始移动
 int rk = -1, ans = 0;
 for (int i = 0; i < n; ++i)
 {
 if (i != 0)
 {
 // 左指针向右移动一格，移除一个字符
 occ.Remove(s[i - 1]);
 }
 while (rk + 1 < n && !occ.Contains(s[rk + 1]))
 {
 // 不断地移动右指针
 occ.Add(s[rk + 1]);
 ++rk;
 }
 // 第 i 到 rk 个字符是一个极长的无重复字符子串
 ans = Math.Max(ans, rk - i + 1);
 }
 return ans;

}

实测还是官方解法秒啊，直接干掉了99%+的提交记录。

最后在简单聊一下做了几道算法题的心得。

首先我还是推荐大家有时间多刷题，我现在是项目一直压着，弄不完，而且自己平时也懒散了些，给自己定的计划就是一周一道题，非常低了，但我每次都会先尽力用自己的方法把题做出来，然后再去看官方的结题思路，之前的两道题都是这样。虽然自己的方法非常粗糙，但通过后，带来的心里慰藉还是非常大的。

另外，其实做算法题，还是像我开始说的，需要抛开经验包袱，这其实就是个考试题，肯定有标准解法，如果你发现你的代码写的比较绕了，或者嵌套的条件非常多了，很大可能是已经走错方向了，除非有特别明确的思路，觉得自己这样一定可以搞出来。就像我这道题一样，我其实做到写List的时候，就觉得肯定结果不会太好，即便通过也是的低效率的。

好了，今天就这样吧，下周继续刷，等忙完这阵，一周多刷几道。

原网站

版权声明
本文为[InfoQ]所创，转载请带上原文链接，感谢
https://xie.infoq.cn/article/b9ac0d8026f296214ee5bce83