代码随想录算法训练营第八天|28. 实现 strStr()，459.重复的子字符串，字符串总结，双指针回顾

系列文章目录

代码随想录算法训练营第一天|数组理论基础，704. 二分查找，27. 移除元素
代码随想录算法训练营第二天|977.有序数组的平方 ，209.长度最小的子数组 ，59.螺旋矩阵II
代码随想录算法训练营第三天|链表理论基础，203.移除链表元素，707.设计链表，206.反转链表
代码随想录算法训练营第四天|24. 两两交换链表中的节点，19.删除链表的倒数第N个节点，面试题 02.07. 链表相交，142.环形链表II，总结
代码随想录算法训练营第五天|哈希表理论基础，242.有效的字母异位词，349. 两个数组的交集，202. 快乐数，1. 两数之和
代码随想录算法训练营第六天|454.四数相加II，383. 赎金信，15. 三数之和，18. 四数之和，总结
代码随想录算法训练营第七天|344.反转字符串，541. 反转字符串II，卡码网：54.替换数字，151.翻转字符串里的单词，卡码网：55.右旋转字符串

---

28.实现strStr()

题目链接： 28.实现strStr()
**题目内容：**给你两个字符串 haystack 和 needle ，请你在 haystack 字符串中找出 needle 字符串的第一个匹配项的下标（下标从 0 开始）。如果 needle 不是 haystack 的一部分，则返回 -1 。
视频讲解：帮你把KMP算法学个通透！（理论篇）；帮你把KMP算法学个通透！（求next数组代码篇）

核心思想：KMP算法

class Solution:
    def getNext(self,next:List[int],s:str) -> None:
        #初始化next数组
        next[0]=0
        j=0
        #(j是前缀末尾，i是后缀末尾)
        for i in range(1,len(s)):
            #处理不同情况的前后缀
            while j>0 and s[i]!=s[j]:
                j=next[j-1]
            #处理相同情况的前后缀
            if s[i]==s[j]:
                j+=1
            #更新next数组
            next[i]=j

    def strStr(self, haystack: str, needle: str) -> int:
        #needle字符串的长度为0的情况
        if len(needle) == 0:
            return 0
        #初始化next数组
        next=[0]*len(needle)
        #生成next数组
        self.getNext(next,needle)
        j=0
        #遍历haystack字符串
        for i in range(len(haystack)):
            #匹配不上时，回撤
            while j>0 and haystack[i]!=needle[j]:
                j=next[j-1]
            #匹配上时，继续向前匹配
            if haystack[i]==needle[j]:
                j+=1
            #匹配完成，输出下标
            if j==len(needle):
                return i-len(needle)+1
        return -1

459.重复的子字符串

题目链接： 459.重复的子字符串
**题目内容：**给定一个非空的字符串 s ，检查是否可以通过由它的一个子串重复多次构成。
视频讲解：字符串这么玩，可有点难度！ | LeetCode：459.重复的子字符串

移动匹配法：

class Solution:
    def repeatedSubstringPattern(self, s: str) -> bool:
        n=len(s)
        if n<=1:
            return False
        ss=s[1:]+s[:-1]
        print(ss.find(s))
        return ss.find(s)!=-1

KMP算法：

class Solution:
    def repeatedSubstringPattern(self, s: str) -> bool:
        if len(s)==0:
            return False
        next=[0]*len(s)
        self.getNext(next,s)
        if next[-1]!=0 and len(s)%(len(s)-next[-1])==0:
            return True
        return False

    def getNext(self,next,s):
        #初始化next数组
        next[0]=0
        j=0
        for i in range(1,len(s)):
            #处理不同前后缀的情况
            while j>0 and s[i] != s[j]:
                j=next[j-1]
            #处理相同前后缀的情况
            if s[i]==s[j]:
                j+=1
            #更新next数组
            next[i]=j
        return next

字符串总结

1. 字符串是若干字符组成的有限序列，也可以理解为是一个字符数组；
2. 如果题目关键的部分直接用库函数就可以解决，建议不要使用库函数；如果库函数仅仅是解题过程中的一小部分，并且你已经很清楚这个库函数的内部实现原理的话，可以考虑使用库函数；
3. 双指针法在数组，链表和字符串中都很常用；
4. 很多数组填充类的问题，都可以先预先给数组扩容带填充后的大小，然后在从后向前进行操作；
5. KMP的主要思想是当出现字符串不匹配时，可以知道一部分之前已经匹配的文本内容，可以利用这些信息避免从头再去做匹配了。

双指针回顾

（一）数组

双指针法效率的优势：通过两个指针在一个for循环下完成两个for循环的工作。
在原地移除数组上的元素时，数组上的元素不能真正的删除，只能覆盖，因此可以采用双指针法。

（二）字符串

1. 反转字符串：使用双指针法，定义两个指针（也可以说是索引下标），一个从字符串前面，一个从字符串后面，两个指针同时向中间移动，并交换元素；
2. 替换空格：数组（字符串）填充类的问题，都可以先预先给数组扩容带填充后的大小，然后使用双指针法从后向前进行操作；
3. 在删除冗余空格的过程中，如果不注意代码效率，很容易写成了O(n^2)的时间复杂度。其实使用双指针法O(n)就可以搞定。

（三）链表

1. 使用双指针法来翻转链表，只需要改变链表的next指针的指向，直接将链表反转 ，而不用重新定义一个新的链表；
2. 在链表中求环时可以用双指针法判断是否有环，并且找到环的入口。

（四）N数之和

1. 使用双指针法通过前后两个指针不断向中间逼近可以在一个for循环下完成两个for循环的工作；
2. 三数之和使用双指针法就是将原本暴力O($n^3$)的解法，降为O($n^2$)的解法，四数之和的双指针解法就是将原本暴力O($n^4$)的解法，降为O($n^3$)的解法；
3. 五数之和，n数之和都是在这个基础上累加。