0028.找出字符串中第一个匹配项的下标
难度：🟢 简单
标签：字符串、双指针
题目描述
给你两个字符串 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 。
解题思路
核心思想
本题的目标是在一个主字符串 (haystack) 中查找一个模式字符串 (needle) 首次出现的位置。这是一个经典的字符串匹配问题。
思路选择
暴力匹配法（滑动窗口） 是解决此问题最直观的思路。
我们可以想象一个长度与
needle相同的“窗口”在haystack上滑动。从
haystack的第一个字符开始，我们将窗口内的子串与needle进行逐一字符的比较。如果完全匹配，就返回窗口的起始索引。
如果不匹配，就将窗口向右滑动一位，继续比较，直到找到匹配或者
haystack遍历完毕。
更高级的算法如 KMP 算法 可以通过预处理 needle 字符串来避免在匹配失败时不必要的回溯，从而在特定情况下获得更高的效率，但对于本题，暴力匹配已足够。
关键步骤
处理边界情况：如果
needle是空字符串，根据题意应返回 0。主循环：外层循环遍历
haystack，作为窗口的起始位置i。循环的上界是haystack.length - needle.length，因为再往后haystack剩余的长度已不足以容纳needle。窗口内比较：对于每一个起始位置
i，启动一个内层循环，比较从haystack[i]开始的子串与needle的每一个字符是否相等。判断与返回： a. 如果在内层比较中出现不匹配的字符，则立即中断内层循环，进入下一个外层循环（即窗口右移一位）。 b. 如果内层循环顺利完成（即所有字符都匹配），说明找到了第一个匹配项，直接返回窗口的起始索引
i。未找到：如果外层循环结束后仍未返回，说明
haystack中不存在needle，返回-1。
代码实现 (推荐)
/**
* @param {string} haystack
* @param {string} needle
* @return {number}
*/
var strStr = function(haystack, needle) {
if (needle.length === 0) {
return 0;
}
const n = haystack.length;
const m = needle.length;
// 遍历所有可能的起始点
for (let i = 0; i <= n - m; i++) {
let matched = true;
// 比较窗口内的子串与 needle
for (let j = 0; j < m; j++) {
if (haystack[i + j] !== needle[j]) {
matched = false;
break;
}
}
// 如果完全匹配，返回起始索引
if (matched) {
return i;
}
}
return -1;
};
原始代码分析 (用户提供)
您提供的代码是此问题的标准暴力解法，逻辑完全正确。
/**
* @param {string} haystack
* @param {string} needle
* @return {number}
*/
var strStr = function (haystack, needle) {
// 外层循环，i 是窗口的起始点
for (let i = 0; i < haystack.length - needle.length + 1; i++) {
// 检查窗口的第一个字符是否匹配，可以作为一种微小的优化
if (haystack[i] === needle[0]) {
let j = 1;
// 内层循环，比较后续字符
for (j; j < needle.length; j++) {
if (haystack[i + j] !== needle[j]) break;
}
// 如果内层循环正常结束，说明匹配成功
if (j === needle.length) return i;
}
}
return -1;
};
- 优点：此实现是暴力匹配的直接体现，逻辑清晰。通过先判断首字符
haystack[i] === needle[0]，可以在首字符不匹配时直接跳过内层循环，是一种有效的优化。
复杂度分析
时间复杂度：O(m × n) 其中 m 是
haystack的长度，n 是needle的长度。在最坏的情况下（例如haystack = "aaaaaab",needle = "aab"），对于haystack的每个起始位置，我们都可能需要完整地比较一次needle的长度。空间复杂度：O(1) 我们只使用了常数个额外变量，空间消耗是恒定的。
相关题目
总结
本题是字符串匹配的基础题目，暴力解法是必须掌握的。通过双层循环模拟“滑动窗口”进行比较，虽然不是最高效的算法，但思路简单直观，足以应对大多数情况。了解 KMP 等更高级的算法，可以作为对字符串问题深入理解的拓展。