1 问题描述

给你两个字符串 haystack 和 needle ，请你在 haystack 字符串中找出 needle 字符串出现的第一个位置（下标从 0 开始）。如果不存在，则返回  -1 。

示例 1:

输入: haystack = "hello", needle = "ll"
输出: 2

示例 2:

输入: haystack = "aaaaa", needle = "bba"
输出: -1

示例 2:

输入: haystack = "", needle = ""
输出: 0

from typing import List
class Solution:
    def strStr(self, haystack: str, needle: str) -> int:
        #在此之间填写代码

print(Solution().strStr("hello","ll"))
print(Solution().strStr("aaaaa", needle = "bba"))
print(Solution().strStr(haystack = "", needle = ""))

View Code

2 解题思路

• 标签：字符串
• 使用滑动窗口，判断haystack字符串中与needle长度相等的窗口是否与needle一样

#3 解题方法

from typing import List
class Solution:
    def strStr(self, haystack: str, needle: str) -> int:
        j=0
        a,b=len(haystack),len(needle)
        if b==0:return 0
        while j<a:
            if haystack[j:j+b]==needle:
                return j
            j+=1
        return -1

print(Solution().strStr("hello","ll"))
print(Solution().strStr("aaaaa", needle = "bba"))
print(Solution().strStr(haystack = "", needle = ""))

View Code

第1-3，13-15行： 题目中已经给出的信息，运行代码时要根据这些代码进行编辑
第4行： 定义变量j=0用于滑动窗口左边框索引
第5行： 定义变量a，b分别存放字符串haystack和字符串needle的长度
第6行： 若needle字符串长度等于0，则直接返回0
第7行： 当索引j小于字符串haystack长度时，执行循环
第8行： 判断字符串haystack从j到j+b即长度为b的切片是否与needle相等
第9行： 若相等，则返回j的值
第10行： 若不想等，j值加一并执行下次循环
第11行： 若直到最后都没有返回值，则返回-1

代码运行结果为：

#算法讲解

这里用到了基础技巧：滑动窗口，简单讲解下这个技巧：
什么是滑动窗口
滑动窗口，顾名思义，就是有一个大小可变的窗口，左右两端方向一致的向前滑动（右端固定，左端滑动；左端固定，右端滑动）。
可以想象成队列，一端在push元素，另一端在pop元素，如下所示：

假设有数组[a b c d e f g h]
一个大小为3的滑动窗口在其上滑动,则有:
[a b c]
  [b c d]
    [c d e]
      [d e f]
        [e f g]
          [f g h]

适用范围
- 1、一般是字符串或者列表
- 2、一般是要求最值（最大长度，最短长度等等）或者子序列
算法思想
- 1、在序列中使用双指针中的左右指针技巧，初始化 left = right = 0，把索引闭区间 [left, right] 称为一个窗口。
- 2、先不断地增加 right 指针扩大窗口 [left, right]，直到窗口中的序列符合要求。
- 3、此时，停止增加 right，转而不断增加 left 指针缩小窗口 [left, right]，直到窗口中的序列不再符合要求。同时，每次增加 left前，都要更新一轮结果。
- 4、重复第 2 和第 3 步，直到 right 到达序列的尽头。

思路其实很简单：第 2 步相当于在寻找一个可行解，然后第 3 步在优化这个可行解，最终找到最优解。左右指针轮流前进，窗口大小增增减减，窗口不断向右滑动。