鲁迅说过，春节过后，依然要加强学习，不断提高自己。每天一道二哥的 LeetCode 刷题笔记，精神百倍。先用 String 的 indexOf() 方法实现方式来 strStr() 方法，然后再用 KMP 算法来实现一遍，酸爽极了。

题意

给你两个字符串 haystack 和 needle ，请你在 haystack 字符串中找出 needle 字符串的第一个匹配项的下标（下标从 0 开始）。如果 needle 不是 haystack 的一部分，则返回 -1 。

难度

简单

示例

例 1

输入：haystack = "sadbutsad", needle = "sad"
输出：0
解释："sad" 在下标 0 和 6 处匹配。
第一个匹配项的下标是 0 ，所以返回 0 。

例 2

输入：haystack = "leetcode", needle = "leeto"
输出：-1
解释："leeto" 没有在 "leetcode" 中出现，所以返回 -1 。

分析 1

对于这道题，我们很容易想到 Java 字符串的indexOf()方法，我在二哥的 Java 进阶之路上也帮大家讲过这个方法的实现。

那题解立马就有了，嘿嘿 😜。

class Solution {
    public int strStr(String haystack, String needle) {
        int index = haystack.indexOf(needle);
        return index;
    }
}

并且题解效率非常高：

直接就击败 100% 的 Java 用户。

分析 2

不过 LeetCode 出这道题，显然不是为了让我们直接调用indexOf()方法，而是让我们去实现一个indexOf()方法。

既然如此，我们不妨再来看一下 indexOf 方法的源码（最终 indexOf(String str) 调用的方法）：

JDK8 版本的方法签名是：

static int indexOf(char[] source, int sourceOffset, int sourceCount,
            char[] target, int targetOffset, int targetCount,
            int fromIndex)

先来看参数：

• source：主字符串的字符数组。
• sourceOffset：主字符串的起始偏移量。
• sourceCount：主字符串中字符的总数。
• target：要查找的子字符串的字符数组。
• targetOffset：子字符串的起始偏移量。
• targetCount：子字符串中字符的总数。
• fromIndex：开始搜索的索引位置。

再来看逻辑流程：

• 首先，检查fromIndex是否大于或等于sourceCount。如果是，且targetCount为 0，则返回sourceCount；否则返回-1。
• 如果fromIndex小于 0，它被设置为 0。
• 如果targetCount为 0，则直接返回fromIndex，因为空字符串被认为存在于任何位置。
• 然后，计算最大搜索索引max，这是为了确保搜索时target能够完全位于source中。
• 接下来，遍历source数组，从sourceOffset + fromIndex开始，直到max，查找与target数组中第一个字符匹配的字符。
• 一旦找到第一个匹配的字符，就在source中从这个位置开始，尝试匹配整个target数组。
• 如果所有后续字符都匹配，就返回当前的索引（调整过的，即i - sourceOffset），因为这表示找到了完整的子字符串。
• 如果遍历完成后未找到匹配的子字符串，则返回-1。

这种实现方式在处理大字符串时效率不如KMP（Knuth-Morris-Pratt）算法，但 JDK 选择了这种更易于理解和实现的方法，足以处理大多数常见的情况。

所以，我们可以按照这个思路来实现我们的strStr()方法。

class Solution {
    public int strStr(String haystack, String needle) {
        // 获取主字符串和子字符串的长度
        int sourceCount = haystack.length();
        int targetCount = needle.length();
        
        // 如果子字符串为空，则根据题目要求返回0
        if (targetCount == 0) {
            return 0;
        }
        
        // 获取子字符串的第一个字符，用于后续匹配的起点
        char first = needle.charAt(0);
        // 计算搜索的最大起始位置，确保子字符串能够完全位于主字符串中
        int max = sourceCount - targetCount;
        
        // 遍历主字符串
        for (int i = 0; i <= max; i++) {
            // 寻找与子字符串第一个字符匹配的字符
            if (haystack.charAt(i) != first) {
                // 如果当前字符不匹配，继续向后搜索直到找到匹配的字符或达到最大索引
                while (++i <= max && haystack.charAt(i) != first);
            }
            
            // 找到第一个字符后，检查剩余的部分是否也匹配
            if (i <= max) {
                int j = i + 1; // 设置匹配的下一个字符的索引
                int end = j + targetCount - 1; // 计算子字符串在主字符串中的结束位置
                for (int k = 1; j < end && haystack.charAt(j) == needle.charAt(k); j++, k++);
                // 如果整个子字符串都匹配了，返回其在主字符串中的起始索引
                if (j == end) {
                    return i;
                }
            }
        }
        // 如果遍历完成后没有找到匹配的子字符串，返回-1
        return -1;
    }
}

如果觉得上面的代码有点复杂，我们可以稍微简化一下：

class Solution {
    public int strStr(String haystack,