算法养成记：实现 strStr()
呆萌程序员
算法养成记
LeetCode28
Implement strStr()
Implement strStr().
Return the index of the first occurrence of needle in haystack, or -1 if needle is not part of haystack.
Example 1:
Input: haystack = "hello", needle = "ll"
Output: 2
Example 2:
Input: haystack = "aaaaa", needle = "bba"
Output: -1
Clarification:
What should we return when needle is an empty string? This is a great question to ask during an interview.
For the purpose of this problem, we will return 0 when needle is an empty string. This is consistent to C's strstr() and Java's indexOf().
中文意思就是：
实现 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() 定义相符。
暴力**！
遍历haystack的每一个字符
当某一位置i的字符和needle的第一个字符相等时，再依次判断下一个字符与needle的下一个字符是否相等
注意跳出循环的条件，当i+needle.length>haystack.length时，就意味着后面不可能相等了，所以可以提前跳出循环
当某循环的长度等于needle.length，就意味着已经找到了第一个相等的字符换，可以跳出循环。
所以代码如下：
用Java的话，偷个懒，用substring方法直接截取haystack和needle长度相同的字符串，依次比较；大于haystack.length-needle.length时，查找失败，跳出循环。
当我在查查别人还有没有什么好方法时，看到了一个说只用一行代码，执行0ms。还满怀期待的点了进去，然后我看到了如下触目惊心的代码！
当时好想抽那位仁兄一个大嘴瓜子，简直沙雕一般的存在，也是没救了的。
以下是JDK的源码：
从源码上看，首先是找了第一个相等的字符，找了之后，再依次找之后的字符，从思想上还是一样的。
在实际测试里
执行用时分别是：1ms,0ms,0ms
内存消耗分别是:38.2MB,37.9MB,38.3MB
欢迎各位小伙伴加微信：miraclesComing一起算题学算法呀！