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

题目：28. 找出字符串中第一个匹配项的下标

输入：haystack = "sadbutsad", needle = "sad"
输出：0
解释："sad" 在下标 0 和 6 处匹配。第一个匹配项的下标是 0 ，所以返回 0 。

输入：haystack = "leetcode", needle = "leeto"
输出：-1
解释："leeto" 没有在 "leetcode" 中出现，所以返回 -1 。

解题思路

见代码。

实现代码

package leetcodefunc strStr(haystack string, needle string) int {//needle为空，返回0，惯例if needle == "" {return 0}//haystack为空，返回-1；如果haystack长度小于needle，返回-1，都是惯例if haystack == "" || len(haystack) < len(needle) {return -1}//needle长度subLen := len(needle)//求出的差值代表遍历的范围，如果超出此值，再从haystack截取出来的字符串肯定比needle短（就是不相等）beginLen := len(haystack) - subLenfor i := 0; i < beginLen; i++ {if haystack[i:i+subLen] == needle {return i}}return -1
}

复杂度分析

• 时间复杂度: 最坏情况下，算法需要遍历 haystack 的每个位置，并对比长度为 subLen 的子串。因此，时间复杂度为 $ O((n-m)*m) $ ，其中 n 是 haystack 的长度，m 是 needle 的长度
• 空间复杂度: 空间复杂度为 $ O(1) $ ，因为算法只使用了常数级别的额外空间来存储一些变量。

单元测试

package leetcodeimport ("testing""github.com/stretchr/testify/assert"
)func Test_strStr(t *testing.T) {assert := assert.New(t)type args struct {haystack stringneedle   string}tests := []struct {args argswant int}{{args: args{haystack: "sadbutsad", needle: "sad"},want: 0,},{args: args{haystack: "leetcode", needle: "leeto"},want: -1,},}for _, tt := range tests {actual := strStr(tt.args.haystack, tt.args.needle)assert.Equal(tt.want, actual)}
}

• 知识星球：云原生AI实战营。10+ 高质量体系课（ Go、云原生、AI Infra）、15+ 实战项目，P8 技术专家助你提高技术天花板，冲击百万年薪！
• 公众号：令飞编程，分享 Go、云原生、AI Infra 相关技术。回复「资料」免费下载 Go、云原生、AI 等学习资料；
• 哔哩哔哩：令飞编程 ，分享技术、职场、面经等，并有免费直播课「云原生AI高新就业课」，大厂级项目实战到大厂面试通关；