找出字符串中第一个匹配项的下标

一、题目

给定：

haystack = "sadbutsad"
needle   = "sad"

在 haystack 中寻找 needle 第一次出现的位置。

结果：

0

如果不存在：

-1

---

二、核心思路

这道题直接使用暴力匹配。

从 haystack 的每一个可能位置开始：

haystack：s a d b u t s a d
          ↑
          i

假设当前 i 是匹配起点，就让 j 从 0 开始：

haystack[i + j]
needle[j]

逐个比较。

例如：

haystack = sadbutsad
needle   = sad

i = 0

haystack[0] == needle[0]  → s == s
haystack[1] == needle[1]  → a == a
haystack[2] == needle[2]  → d == d

全部相同，说明匹配成功，直接返回 i。

---

三、代码

int strStr(char *haystack, char *needle)
{
    int n1 = strlen(haystack);
    int n2 = strlen(needle);

    // needle 为空，按照题目约定返回 0
    if (n2 == 0)
        return 0;

    // needle 比 haystack 还长，不可能匹配
    if (n2 > n1)
        return -1;

    // i：当前尝试匹配的起始位置
    //
    // 例如：
    // haystack 长度 = 9
    // needle   长度 = 3
    //
    // i 最多到 6
    // 因为从 7 开始，剩余只有 2 个字符，
    // 已经放不下长度为 3 的 needle
    for (int i = 0; i <= n1 - n2; i++)
    {
        int j;

        // j：比较 needle 中第几个字符
        for (j = 0; j < n2; j++)
        {
            // haystack[i + j]
            // 表示：从 haystack[i] 开始往后数 j 个字符
            //
            // 例如 i = 3，j = 2
            // 比较的就是 haystack[5]
            if (haystack[i + j] != needle[j])
            {
                // 当前起点匹配失败
                // 不需要继续比较，直接换下一个 i
                break;
            }
        }

        // j == n2
        // 说明 needle 的所有字符都比较成功
        if (j == n2)
            return i;
    }

    // 所有可能的起点都尝试过，但都没有匹配成功
    return -1;
}

---

四、最关键的一句

haystack[i + j]

它表示：

以 i 为起点，比较当前位置 j 的字符。

例如：

haystack = "abcdef"
needle   = "cd"

i = 2

那么：

j = 0 → haystack[2] == needle[0]
j = 1 → haystack[3] == needle[1]

也就是：

c d
↑ ↑

---

五、为什么 i <= n1 - n2

这是这道题另一个关键点。

例如：

haystack = "abcdef"
needle   = "def"

长度：

n1 = 6
n2 = 3

那么 i 最大只能是：

6 - 3 = 3

因为：

i = 3

刚好：

d e f

如果：

i = 4

只有：

e f

剩余长度不够放完整的 needle。

所以：

i <= n1 - n2

而不是：

i < n1

---

六、匹配失败怎么处理？

例如：

haystack = "sadbutsad"
needle   = "sat"

第一次：

i = 0

s == s
a == a
d != t

于是：

break;

退出内层循环。

然后：

i++

继续从下一个位置尝试。

所以整体过程就是：

i = 0 → 匹配
        ↓失败
i = 1 → 匹配
        ↓失败
i = 2 → 匹配
        ↓失败
...
        ↓
找到 → return i

---

七、为什么 j == n2 就代表成功？

因为：

for (j = 0; j < n2; j++)

正常执行完，意味着：

j = 0 → 匹配
j = 1 → 匹配
j = 2 → 匹配
...
j = n2 - 1 → 匹配

最终：

j == n2

说明 needle 的所有字符都匹配成功。

所以：

if (j == n2)
    return i;

---

八、整体逻辑

记住这两个变量：

i：换一个位置重新开始匹配
j：当前位置逐字符比较

整个算法：

i 选择起点
↓
j 逐个比较
↓
不同 → break → i++
↓
全部相同 → return i
↓
所有位置都失败 → return -1

九、复杂度

设：

n = haystack 长度
m = needle 长度

最坏情况下：

时间复杂度：O(n × m)
空间复杂度：O(1)

这道题本质就是：

枚举匹配起点 + 逐字符比较。