题目Implement strStr().Return the index of the first occurrence of needle in haystack, or-1if needle is not part of haystack.Example 1:Input: haystack hello, needle ll Output: 2Example 2:Input: haystack aaaaa, needle bba Output: -1Clarification:What should we return whenneedleis an empty string? This is a great question to ask during an interview.For the purpose of this problem, we will return 0 whenneedleis an empty string. This is consistent to Cs strstr() and Javas indexOf().这道题是让你返回haystack中needle的位置如果needle不是haystack的substring的话则返回-1needle为空时返回0。这道题的普通思路很好想就暴力遍历haystack看看有没有匹配的。我自己写的代码如下运行时间312ms只超越了20%的submission……class Solution { public: int strStr(string haystack, string needle) { if (needle ) return 0; bool found true; for (int i 0; i haystack.length(); i) { found true; if (haystack[i] needle[0]) { for (int j 1; j needle.length(); j) { if (haystack[i j] ! needle[j]) { found false; break; } } if (found) { return i; } } } return -1; } };然而我这里用到的方法并不是最优雅的写法主要有两个地方可以改进1. 在遍历heystack的时候不需要遍历整个字符串只需要遍历到haystack.length() - needle.length()即可2. 并不需要像我上面那样先判断首字母是否相同可以直接开始比较并且不需要设置bool found可以直接判断j是否到达了needle的结尾刚开始第一次就被found坑了设完false以后忘记在重新回去遍历heystack的时候设回true导致一次匹配不成功后面的就算成功也只能返回-1改进后的代码如下运行时间突然就缩短到了4msclass Solution { public: int strStr(string haystack, string needle) { if (needle ) return 0; if (haystack.length() needle.length()) return -1; for (int i 0; i haystack.length() - needle.length(); i) { int j; for (j 0; j needle.length(); j) { if (haystack[i j] ! needle[j]) { break; } } if (j needle.length()) { return i; } } return -1; } };本来以为改一下很简单结果提交了两次WA的……发现有几个坑在里面1. 需要提前判断haystack和needle的长度大小如果needle比haystack还长那就直接返回-1这个在我上面的写法中是不需要的2. 在遍历haystack的时候边界应该是而不是不然二者长度相等的情况就会被排除在外另外一种神奇的方法就是我第一次听说的KMP算法孤陋寡闻了但是看了一些博客纷纷表示这道题的本意就是让你brute-force并不需要KMP因为比较复杂而且代码比较难写于是我就决定只了解KMP算法的思想懒得去实现代码了orz这个心态不对。结果发现看完一个视频和一篇文章后还是完全不知道它在干什么……遂放弃觉得这应该不是我目前的当务之急等到把真·基础知识都补完了以后再回来填坑吧。以下贴几个相关链接1. YouTube小哥的讲解https://www.youtube.com/watch?vBXCEFAzhxGY 视频时长一共17分钟KMP正片开始是2:4515分钟以后是分析算法复杂度的因此其实讲解的一共只有12分钟也不算太长吧orz这个小哥前几天还看过他讲merge two sorted lists的题目看了下他的视频有挺多都是讲算法的感觉讲的还行以后可以关注一下2. KMP in C, explanation includedhttps://leetcode.com/problems/implement-strstr/discuss/12883/KMP-in-C%2B%2B-explanation-included 有代码也有解释看起来还行3. KMP算法详解KMP算法详解 | Matrix67: The Aha Moments4. C Brute-Force and KMPhttps://leetcode.com/problems/implement-strstr/discuss/12956/C%2B%2B-Brute-Force-and-KMP2025.3.18随便第一页挑个easy只剩这个了嗯直接把题理解错了implement出来一个别的东西……还是只能brute force了但是和N年前比有进步。虽然还是掉进了判断长度的坑里啊。class Solution { public int strStr(String haystack, String needle) { for (int i 0; i haystack.length(); i) { for (int j 0; j needle.length(); j) { if (i j haystack.length() || haystack.charAt(i j) ! needle.charAt(j)) { break; } if (j needle.length() - 1) { return i; } } } return -1; } }2026.8.21再来复习以为自己熟悉2 pointers了但是这题不是那么标准的2 pointers就掉进坑里了。刚开始写了俩while结果发现这个case过不去haystack mississippineedle issip因为真正的match issip的时候前面的i在第一次我match issi的那段然后因为我一直在移动haystack里的指针所以发现第一个issi后面接的不是p以后我又接着移就没法考虑进最后那个i其实是真正match的第一个字符。然后折腾出来一个nested while的解法又掉进了haystack长度的坑这个就好解决改了一下终于过了。看了这篇笔记又开始折腾for的写法结果又掉进长度的坑里了。脑子不转了。下次还是得复习别又进同一个坑了。