让我们一起啃算法---- 实现 strStr

实现 strStr（Implement-StrStr）

题干如下：

实现 strStr() 函数。

给定一个 haystack 字符串和一个 needle 字符串，在 haystack 字符串中找出 needle 字符串出现的第一个位置 (从0开始)。如果不存在，则返回  -1。

示例 1:

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

输出: 2

示例 2:

输入: haystack = "aaaaa", needle = "bba"

输出: -1

说明:

当 needle 是空字符串时，我们应当返回什么值呢？这是一个在面试中很好的问题。

对于本题而言，当 needle 是空字符串时我们应当返回 0 。这与C语言的 strstr() 以及 Java的 indexOf() 定义相符。

来源：力扣

本题有很多种解题方式，为了再巩固一下 双指针解题思路 这题我们还是选用这种思路来解。

建议再结合 让我们一起啃算法----移除元素 和 让我们一起啃算法----删除排序数组中的重复项 两篇文章仔细体会一下 双指针思路 。

解题思路

初始化 i 指向 needle 字符串的第一个字符， j 指向 haystack 字符串的第一个字符。比较 needle[i] 与 haystack[j] 的字符是否相等：相等则 i++、j++ ；不想等则 i 重新指向 needle 字符串的第一个字符， j 指向上一次初始位置的后一个字符。

注： j 指向上一次初始位置的后一个字符的计算方式为： j = j - i + 1。可以自己造个数组，推算一下这个规律哟。

流程图如下：

代码实现

GO语言实现

func strStr(haystack string, needle string) int {

    // 子串为空则返回 0
    if needle == "" {
        return 0
    }

    i := 0
    j := 0
    for j < len(haystack) {
        // 判断 haystack[j] 与 needle[i] 是否相等，不想等，则 i 重新指向 needle 字符串的首字符，即 i = 0
        // j 指向 j上一次初始化的后一个字符串，即 j = j - i + 1
        if haystack[j] != needle[i] {
            j = j - i + 1
            i = 0
        } else {
            // haystack[j] 与 needle[i] 相等，则先判断 i 是否已经最大
            // 是的话就返回 needle 在 haystack 的第一个位置，计算方式： j - i
            if i == len(needle) -1 {
                return j - i
            }
            // 如果 i 不是 needle 的最大索引，那么 j 向后移动一位，i 向后移动一位，继续比较
            j++
            i++
        }
    }
    // j 越界了，说明不存在子串 needle，即返回 -1
    return -1
}

总结