strStr
作为刷提笔记第一道题，其实还是有很多东西值得参考的，相对于其他的题目，字符串操作类的题目很容易把边界条件的加减搞错。要注意以下几点：
1. 当要以两个字符串长度相减作为结束点是一定要"source.length() - target.length() +1"因为减的结果是最后一个字符所在的位置，而不是最后一个字符后面一位。
2.当输入等于null时一定要问清面试官到底要返回值是什么。
这是第一种算法，第二种是取模算法，第三种是KMP
取模算法的核心思想是sliding window，主要分为以下三个步骤：
1.loop over 通过公式算出target的密码模。
2.loop over整个string然后每个字符不断取模，当到达target相同个数字符之后比较与target模是否相同，如果相同的话就再比较字符串字符。当string里比较字符的个数超过target的个数就扔掉前面的字符的模然后继续比较。
这样做的时间复杂度近似于m+n，因为当两个字符串模相同的情况一般情况下就是两个字符串相等的情况（哈希碰撞）
程序：
KMP核心思想就是先找出target字符串中重复的部分，然后loop over字符串，当比较前面位相同时，从重复的最后一段开始继续往后面比较，这样的时间复杂度是M+N
但是总感觉上面的这种方法2更简单易于理解
网友评论