从零打卡刷Leetcode

资源干货第一时间送达！

写在前边：

小詹一直觉得自己编程能力不强，想在网上刷题，又怕不能坚持。不知道有木有和小伙伴和小詹一样想找个人一起刷题呢？欢迎和小詹一起定期刷leetcode，每周一周五更新一题，每一题都吃透，欢迎一题多解，寻找最优解！欢迎小伙伴们把自己的思路在留言区分享出来噢

上一期有留一个小bug让小伙伴们找，不知道多少人自己找到了啊？爱学习的人肯定自己去尝试了，肯定发现leetcode上运行结果发现输出不是预期的[7, 0, 8]，而是像下边这样：

一个不合预期的地方是出现了小数，还有一个则是链表长度不合预期。其实，这个是除法导致的，这里的除法保留了小数部分，导致进位标志carry不是我们需要的整型0或者1了，所以出现了小数，另一方面进位的错误也导致在最高位的时候再次进了一位，即链表中多出了个1。修改方法很简单，只需要在两处carry位置进行类型转换，具体如下。或者注意''/''和“//”的区别，后者所除的结果仅保留商（整型），前者即存在小数。

上期没找出原因的小伙伴可以去改过来试试看噢~

No.3 Longest Substring without Repeating Characters

原题：

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

题目大意：给出一个字符串，找到最长的没有重复字符的子字符串，并返回该子字符串的长度。

例如：

可能是前边的题目都大同小异，难度也接近。也有可能是人的思维有惯性，小詹又是利用循环嵌套遍历所有情况进行判断的，这种简单粗暴可以实现，但是效率很低。大体思路是：第一层循环从字符串的最左侧到最右侧第二个，即for i in range(0,len(s)-1)，第二层循环则从第一层紧跟着的一个到最后一个字符。即for j in range(i+1,len(s));之后通过找出所有不重复的子字符串，比较长度得到最大长度的子字符串。代码如下：（需要注意当字符串长度为0或1的特殊情况）

结果当然是可以通过的啦，然而时间效率方面很差很差，如图：

然而，我们不能满足于这种最低效率的实现结果。下边提出一个炒鸡牛逼的方法，非原创，小詹花了很久才搞明白其思路，其利用到了字典的方法。什么是字典？请自行补充知识噢（公众号有语法综述）。先放代码后再解释：

代码里对应位置加入了注释，理解起来应该好很多了，这里举例说明下为什么【i - indexDict[s[i]] - 1】代表了当前找到子字符串的长度。

比如字符串'abcdadd'，代码运行过程中一直迭代到i=3【对应字符d】时，都不满足s[i] in indexDict ,不执行条件语句，而是currMax依次加一，并且将字符信息以的形式存放在字典中。当继续迭代i=4时，进入条件语句，这里主要解释【i - indexDict[s[i]] - 1】，检测到了重复字符'a'，之前该字符出现位置为i=0处即【indexDict[s[i]] =0】这时候当前检测到的无重复字符子串为'abcd'，长度为【4-indexDict[s[i]]-1 = 4】。其他同此例。