双指针

1. 双指针简介
2. 双指针相关题目
- 15. 三数之和中等">15. 三数之和中等
- 16. 最接近的三数之和中等">16. 最接近的三数之和中等
- 18. 四数之和中等">18. 四数之和中等
- 80. 删除有序数组中的重复项 II 中等">80. 删除有序数组中的重复项 II 中等
- 189. 轮转数组中等">189. 轮转数组中等
- 151. 翻转字符串里的单词中等">151. 翻转字符串里的单词中等
- 面试题 01.05. 一次编辑中等">面试题 01.05. 一次编辑中等
- 986. 区间列表的交集中等">986. 区间列表的交集中等
- 658. 找到 K 个最接近的元素中等">658. 找到 K 个最接近的元素中等
- 524. 通过删除字母匹配到字典里最长单词中等">524. 通过删除字母匹配到字典里最长单词中等
- 31. 下一个排列中等">31. 下一个排列中等
- 1574. 删除最短的子数组使剩余数组有序中等">1574. 删除最短的子数组使剩余数组有序中等
- 443. 压缩字符串中等">443. 压缩字符串中等
3. kmp算法
- 28. 实现 strStr() 简单">28. 实现 strStr() 简单

1. 双指针简介

双指针，指的是在遍历对象的过程中，不是普通的使用单个指针进行访问，而是使用两个相同方向（快慢指针）或者相反方向（对撞指针）的指针进行扫描，从而达到相应的目的。
换言之，双指针法充分使用了数组有序这一特征，从而在某些情况下能够简化一些运算。

2. 双指针相关题目

15. 三数之和中等

给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有和为 0 且不重复的三元组。
注意：答案中不可以包含重复的三元组。

示例 1：
输入：nums = [-1,0,1,2,-1,-4]
输出：[[-1,-1,2],[-1,0,1]]

示例 2：
输入：nums = []
输出：[]

示例 3：
输入：nums = [0]
输出：[]

提示：
0 <= nums.length <= 3000
-105 <= nums[i] <= 105

题解概要：

1.先排序，再固定一个数，另外两个数使用对撞指针求和。
2.但要注意是如何去重和剪枝的。

代码：

func threeSum(nums []int) [][]int {
    n := len(nums)
    ans := [][]int{}
    if n < 3{
        return ans
    }
    sort.Ints(nums)
    for i := 0;i < n-2;i++{
        //剪枝
        if nums[i] > 0{
            break
        }
        //去重
        if i > 0 && nums[i] == nums[i-1]{
            continue
        }
        l := i + 1
        r := n - 1
        for l < r{
            if nums[i] + nums[l] + nums[r] == 0{
                ans = append(ans,[]int{nums[i],nums[l],nums[r]})
                //去重开始
                for l < r && nums[l] == nums[l+1]{
                    l ++
                }
                for l < r && nums[r] == nums[r-1]{
                    r --
                }
                l ++
                r --
            }else if nums[i] + nums[l] + nums[r] > 0{
                r --
            }else{
                l ++
            }
        }
    }
    return ans
}

16. 最接近的三数之和中等

给你一个长度为 n 的整数数组 nums 和一个目标值 target。请你从 nums 中选出三个整数，使它们的和与 target 最接近。
返回这三个数的和。
假定每组输入只存在恰好一个解。

示例 1：
输入：nums = [-1,2,1,-4], target = 1
输出：2
解释：与 target 最接近的和是 2 (-1 + 2 + 1 = 2) 。

示例 2：
输入：nums = [0,0,0], target = 1
输出：0

提示：
3 <= nums.length <= 1000
-1000 <= nums[i] <= 1000
-104 <= target <= 104

题解概要：

1.先排序，再固定一个数，另外两个数使用对撞指针求和。
2.每次都判断是否与target最接近。

代码：

func threeSumClosest(nums []int, target int) int {
    n := len(nums)
    ans := math.MaxInt32
    sort.Ints(nums)
    for i := 0;i < n-2;i++{
        l := i+1
        r := n-1
        for l < r{
            sum := nums[i] + nums[l] + nums[r]
            if sum == target{
                return sum
            }else if sum > target{
                r --
            }else if sum < target{
                l ++
            }
            if abs(sum-target) < abs(ans-target){
                ans = sum
            }
        }    
    }
    return ans
}
func abs(a int)int{
    if a < 0{
        return -a
    }
    return a
}

给你一个由 n 个整数组成的数组 nums ，和一个目标值 target 。请你找出并返回满足下述全部条件且不重复的四元组 [nums[a], nums[b], nums[c], nums[d]] （若两个四元组元素一一对应，则认为两个四元组重复）：
0 <= a, b, c, d < n
a、b、c 和 d 互不相同
nums[a] + nums[b] + nums[c] + nums[d] == target
你可以按任意顺序返回答案。

示例 1：
输入：nums = [1,0,-1,0,-2,2], target = 0
输出：[[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]

示例 2：
输入：nums = [2,2,2,2,2], target = 8
输出：[[2,2,2,2]]

提示：
1 <= nums.length <= 200
-109 <= nums[i] <= 109
-109 <= target <= 109

题解概要：

1.这道题和三数之和很像，基本一模一样。按照上题思路做即可。
2.也是要注意如何去重。

代码：

func fourSum(nums []int, target int) [][]int {
    n := len(nums)
    ans := [][]int{}
    if n < 4{
        return ans
    }
    sort.Ints(nums)
    for i := 0;i < n - 3;i++{
        //去重
        if i > 0 && nums[i] == nums[i-1]{
            continue
        }
        for j := i + 1;j < n-2;j++{
            //去重
            if j > i + 1 && nums[j] == nums[j-1]{
                continue
            }
            l := j + 1
            r := n - 1
            for l < r{
                if nums[i] + nums[j] + nums[l] + nums[r] == target{
                    ans = append(ans,[]int{nums[i],nums[j],nums[l],nums[r]})
                    for l < r && nums[l] == nums[l+1]{
                        l ++
                    }
                    for l < r && nums[r] == nums[r-1]{
                        r--
                    }
                    l ++ 
                    r --
                }else if nums[i] + nums[j] + nums[l] + nums[r] > target{
                    r --
                }else{
                    l ++
                }
            }
        }
    }
    return ans
}

80. 删除有序数组中的重复项 II 中等

给你一个有序数组 nums ，请你原地删除重复出现的元素，使每个元素最多出现两次，返回删除后数组的新长度。

不要使用额外的数组空间，你必须在原地修改输入数组并在使用 O(1) 额外空间的条件下完成。

说明：

为什么返回数值是整数，但输出的答案是数组呢？

请注意，输入数组是以「引用」方式传递的，这意味着在函数里修改输入数组对于调用者是可见的。

你可以想象内部操作如下:

// nums 是以“引用”方式传递的。也就是说，不对实参做任何拷贝
int len = removeDuplicates(nums);

// 在函数里修改输入数组对于调用者是可见的。
// 根据你的函数返回的长度, 它会打印出数组中该长度范围内的所有元素。
for (int i = 0; i < len; i++) {
print(nums[i]);
}

示例 1：
输入：nums = [1,1,1,2,2,3]
输出：5, nums = [1,1,2,2,3]
解释：函数应返回新长度 length = 5, 并且原数组的前五个元素被修改为 1, 1, 2, 2, 3 。不需要考虑数组中超出新长度后面的元素。

示例 2：
输入：nums = [0,0,1,1,1,1,2,3,3]
输出：7, nums = [0,0,1,1,2,3,3]
解释：函数应返回新长度 length = 7, 并且原数组的前五个元素被修改为 0, 0, 1, 1, 2, 3, 3 。不需要考虑数组中超出新长度后面的元素。

提示：
1 <= nums.length <= 3 * 104
-104 <= nums[i] <= 104
nums 已按升序排列

题解概要：

1.使用快慢指针，根据题意做即可。

代码：

func removeDuplicates(nums []int) int {
    i := 1
    n := len(nums)
    t := 1 //需改索引
    a := 0 //同一元素开始的位置
    for i < n{
        //若相邻两个元素不相等
        if nums[i] != nums[a]{
            a = i
        }
        //相邻两个元素相等,判断有没有超过2
        if nums[i] == nums[a] && i-a+1 > 2{
            i++
            continue
        }
        nums[t] = nums[i]
        t ++
        i++
    }
    return t
}

189. 轮转数组中等

给你一个数组，将数组中的元素向右轮转 k 个位置，其中 k 是非负数。

示例 1:
输入: nums = [1,2,3,4,5,6,7], k = 3
输出: [5,6,7,1,2,3,4]
解释:
向右轮转 1 步: [7,1,2,3,4,5,6]
向右轮转 2 步: [6,7,1,2,3,4,5]
向右轮转 3 步: [5,6,7,1,2,3,4]

示例 2:
输入：nums = [-1,-100,3,99], k = 2
输出：[3,99,-1,-100]
解释:
向右轮转 1 步: [99,-1,-100,3]
向右轮转 2 步: [3,99,-1,-100]

提示：
1 <= nums.length <= 105
-231 <= nums[i] <= 231 - 1
0 <= k <= 105

题解概要：

1.使用对撞指针对字符串分段进行翻转。

代码：

func rotate(nums []int, k int)  {
    n := len(nums)
    k %= n
    if n == 1 || k == 0{
        return
    }
    //翻转整个字符串
    reverse(nums,0,n-1)
    //翻转前k个字符串
    reverse(nums,0,k-1)
    //翻转后n-k个字符串
    reverse(nums,k,n-1)
}
func reverse(nums []int,s int,e int){
    for s < e{
        t := nums[s]
        nums[s] = nums[e]
        nums[e] = t
        s ++
        e --
    }
}

151. 翻转字符串里的单词中等

给你一个字符串 s ，逐个翻转字符串中的所有单词。

单词是由非空格字符组成的字符串。s 中使用至少一个空格将字符串中的单词分隔开。

请你返回一个翻转 s 中单词顺序并用单个空格相连的字符串。

说明：
输入字符串 s 可以在前面、后面或者单词间包含多余的空格。
翻转后单词间应当仅用一个空格分隔。
翻转后的字符串中不应包含额外的空格。

示例 1：
输入：s = “the sky is blue”
输出：”blue is sky the”

示例 2：
输入：s = “ hello world “
输出：”world hello”
解释：输入字符串可以在前面或者后面包含多余的空格，但是翻转后的字符不能包括。

示例 3：
输入：s = “a good example”
输出：”example good a”
解释：如果两个单词间有多余的空格，将翻转后单词间的空格减少到只含一个。

示例 4：
输入：s = “ Bob Loves Alice “
输出：”Alice Loves Bob”

示例 5：
输入：s = “Alice does not even like bob”
输出：”bob like even not does Alice”

提示：
1 <= s.length <= 104
s 包含英文大小写字母、数字和空格 ‘ ‘
s 中至少存在一个单词

题解概要：

本题分为三步：
1.去除头尾空格、去除中间空格
2.翻转整个字符串
3.翻转单词

代码：

func reverseWords(s string) string {
    n := len(s)
    b := []byte{}
    //1.去除多余空格
    l,r := 0,n-1
    //去除头部空格
    for l < r && s[l] == ' '{
        l ++
    }
    //去除尾部空格
    for l < r && s[r] == ' '{
        r --
    }
    //去除中间空格
    for l <= r{
        if s[l] != ' '{
            b = append(b,s[l])
        }
        if s[l] == ' ' && b[len(b)-1] != ' '{
            b = append(b,s[l])
        } 
        l ++
    }
    //2.翻转整个字符串
    reverse(b,0,len(b)-1)
    //3.翻转单词
    a := 0
    for i,v := range b{
        if v == ' ' {
            reverse(b,a,i-1)
            a = i+1
        }
    }
    reverse(b,a,len(b)-1)
    return string(b)
}
//翻转字符串
func reverse(b []byte,s int,e int){
    for s < e{
        t := b[s]
        b[s] = b[e]
        b[e] = t
        s ++
        e --
    }
}

面试题 01.05. 一次编辑中等

字符串有三种编辑操作:插入一个字符、删除一个字符或者替换一个字符。给定两个字符串，编写一个函数判定它们是否只需要一次(或者零次)编辑。

示例 1:
输入:
first = “pale”
second = “ple”
输出: True

示例 2:
输入:
first = “pales”
second = “pal”
输出: False

题解概要：

1.由于长串删除字段等于短串增加字段，因此我们永远保证first是长串，则只需要考虑删除一字段或替换一个字段可以使两个字符串相等即可。

代码：

func oneEditAway(first string, second string) bool {
    if first == second{
        return true
    }
    m,n := len(first),len(second)
    //保证first永远是长串
    if m < n{
        first,second = second,first
        m,n = n,m
    }
    if m - n > 1{
        return false
    }
    for i,_ := range second{
          //当元素不同的时候，判断长串删除一个字段或替换一个字段可以使两个字符串相等。
        if first[i] != second[i]{
            return first[i+1:] == second[i:] || first[i+1:] == second[i+1:]
        }
    }
    return true
}

986. 区间列表的交集中等

给定两个由一些闭区间组成的列表，firstList 和 secondList ，其中 firstList[i] = [starti, endi] 而 secondList[j] = [startj, endj] 。每个区间列表都是成对不相交的，并且已经排序。
返回这两个区间列表的交集。

形式上，闭区间 [a, b]（其中 a <= b）表示实数 x 的集合，而 a <= x <= b 。

两个闭区间的交集是一组实数，要么为空集，要么为闭区间。例如，[1, 3] 和 [2, 4] 的交集为 [2, 3] 。

给定两个由一些闭区间组成的列表，firstList 和 secondList ，其中 firstList[i] = [starti, endi] 而 secondList[j] = [startj, endj] 。每个区间列表都是成对不相交的，并且已经排序。

返回这两个区间列表的交集。

形式上，闭区间 [a, b]（其中 a <= b）表示实数 x 的集合，而 a <= x <= b 。

两个闭区间的交集是一组实数，要么为空集，要么为闭区间。例如，[1, 3] 和 [2, 4] 的交集为 [2, 3] 。

示例 1：
输入：firstList = [[0,2],[5,10],[13,23],[24,25]], secondList = [[1,5],[8,12],[15,24],[25,26]]
输出：[[1,2],[5,5],[8,10],[15,23],[24,24],[25,25]]

示例 2：
输入：firstList = [[1,3],[5,9]], secondList = []
输出：[]

示例 3：
输入：firstList = [], secondList = [[4,8],[10,12]]
输出：[]

示例 4：
输入：firstList = [[1,7]], secondList = [[3,10]]
输出：[[3,7]]

提示：
0 <= firstList.length, secondList.length <= 1000
firstList.length + secondList.length >= 1
0 <= starti < endi <= 109
endi < starti+1
0 <= startj < endj <= 109
endj < startj+1

题解概要：

1.区间交集都可以使用下面的思路，先排序，然后使用快慢指针求交集。

代码：

func intervalIntersection(firstList [][]int, secondList [][]int) [][]int {
    ans := [][]int{}
    i,j := 0,0
    for i < len(firstList) && j < len(secondList){
        l := max(firstList[i][0],secondList[j][0]) 
        r := min(firstList[i][1],secondList[j][1])
        if l <= r{
            ans = append(ans,[]int{l,r})
        }
        if firstList[i][1] < secondList[j][1]{
            i ++
        }else{
            j ++
        }
    }
    return ans
}
func max(a,b int)int{
    if a > b{
        return a
    }
    return b
}
func min(a,b int)int{
    if a < b{
        return a
    }
    return b
}

658. 找到 K 个最接近的元素中等

给定一个排序好的数组 arr ，两个整数 k 和 x ，从数组中找到最靠近 x（两数之差最小）的 k 个数。返回的结果必须要是按升序排好的。
整数 a 比整数 b 更接近 x 需要满足：
|a - x| < |b - x| 或者
|a - x| == |b - x| 且 a < b

示例 1：
输入：arr = [1,2,3,4,5], k = 4, x = 3
输出：[1,2,3,4]

示例 2：
输入：arr = [1,2,3,4,5], k = 4, x = -1
输出：[1,2,3,4]

提示：
1 <= k <= arr.length
1 <= arr.length <= 104
数组里的每个元素与 x 的绝对值不超过 104

题解概要：

1.找到k个元素，其实就是删除len(arr) - k这个元素。（不需要真正删除）
2.由于数组是有序的，删除的元素一定位于数组的端部。因此，使用对撞指针即可。

代码：

func findClosestElements(arr []int, k int, x int) []int {
    l,r := 0,len(arr) - 1
    delNum := len(arr) - k
    for delNum > 0{
        if x - arr[l] <= arr[r] - x{
            r --
        }else{
            l ++
        }
        delNum --
    }
    return arr[l:l+k]
}

524. 通过删除字母匹配到字典里最长单词中等

给你一个字符串 s 和一个字符串数组 dictionary ，找出并返回 dictionary 中最长的字符串，该字符串可以通过删除 s 中的某些字符得到。
如果答案不止一个，返回长度最长且字母序最小的字符串。如果答案不存在，则返回空字符串。

示例 1：
输入：s = “abpcplea”, dictionary = [“ale”,”apple”,”monkey”,”plea”]
输出：”apple”

示例 2：
输入：s = “abpcplea”, dictionary = [“a”,”b”,”c”]
输出：”a”

提示：
1 <= s.length <= 1000
1 <= dictionary.length <= 1000
1 <= dictionary[i].length <= 1000
s 和 dictionary[i] 仅由小写英文字母组成

题解概要：

1.先按照长度和字母序对数组排序。
2.再依次遍历每个字符串，看是否满足条件即可。

代码：

func findLongestWord(s string, dictionary []string) string {
    //先根据长度和字典序进行排序
    sort.Slice(dictionary,func(i,j int)bool{
        a,b := dictionary[i],dictionary[j]
        return len(a) > len(b) || (len (a) == len(b) && a < b)
    })
    for _,v := range dictionary{
        i := 0
        for j,_ := range s{
            if s[j] == v[i]{
                i ++
                if i == len(v){
                    return v
                }
            }
        }
    }
    return ""
}

31. 下一个排列中等

整数数组的一个排列就是将其所有成员以序列或线性顺序排列。

例如，arr = [1,2,3] ，以下这些都可以视作 arr 的排列：[1,2,3]、[1,3,2]、[3,1,2]、[2,3,1] 。
整数数组的下一个排列是指其整数的下一个字典序更大的排列。更正式地，如果数组的所有排列根据其字典顺序从小到大排列在一个容器中，那么数组的下一个排列就是在这个有序容器中排在它后面的那个排列。如果不存在下一个更大的排列，那么这个数组必须重排为字典序最小的排列（即，其元素按升序排列）。

例如，arr = [1,2,3] 的下一个排列是 [1,3,2] 。
类似地，arr = [2,3,1] 的下一个排列是 [3,1,2] 。
而 arr = [3,2,1] 的下一个排列是 [1,2,3] ，因为 [3,2,1] 不存在一个字典序更大的排列。
给你一个整数数组 nums ，找出 nums 的下一个排列。

必须原地修改，只允许使用额外常数空间。

示例 1：
输入：nums = [1,2,3]
输出：[1,3,2]

示例 2：
输入：nums = [3,2,1]
输出：[1,2,3]

提示：

1 <= nums.length <= 100
0 <= nums[i] <= 100

题解概要：

1.找到第一个坡顶。
2.找到第一个大于坡顶左侧元素的数，将两个数交换。
3.再将右侧区间进行排序。

从后向前查找第一个相邻升序的元素对 (i,j)，满足 A[i] < A[j]。此时 [j,end) 必然是降序
在 [j,end) 从后向前查找第一个满足 A[i] < A[k] 的 k。A[i]、A[k] 分别就是上文所说的「小数」、「大数」

将 A[i] 与 A[k] 交换

可以断定这时 [j,end) 必然是降序，逆置 [j,end)，使其升序

代码：

func nextPermutation(nums []int)  {
    n := len(nums)
    i := n - 2
    //找到第一个上坡
    for i >= 0 && nums[i] >= nums[i+1]{
        i -- 
    }
    if i >= 0{
        k := n - 1
        //找到[i+1,n]区间第一个大于 i的数k，将i与k进行交换
        for k >= 0 && nums[k] <= nums[i]{
            k --
        }
        nums[i],nums[k] = nums[k],nums[i]
    }
    sort.Ints(nums[i+1:])
}

1574. 删除最短的子数组使剩余数组有序中等

给你一个整数数组 arr ，请你删除一个子数组（可以为空），使得 arr 中剩下的元素是非递减的。
一个子数组指的是原数组中连续的一个子序列。
请你返回满足题目要求的最短子数组的长度。

示例 1：
输入：arr = [1,2,3,10,4,2,3,5]
输出：3
解释：我们需要删除的最短子数组是 [10,4,2] ，长度为 3 。剩余元素形成非递减数组 [1,2,3,3,5] 。
另一个正确的解为删除子数组 [3,10,4] 。

示例 2：
输入：arr = [5,4,3,2,1]
输出：4
解释：由于数组是严格递减的，我们只能保留一个元素。所以我们需要删除长度为 4 的子数组，要么删除 [5,4,3,2]，要么删除 [4,3,2,1]。

示例 3：
输入：arr = [1,2,3]
输出：0
解释：数组已经是非递减的了，我们不需要删除任何元素。

示例 4：
输入：arr = [1]
输出：0

提示：
1 <= arr.length <= 10^5
0 <= arr[i] <= 10^9

题解概要：

1.从左往右找递增序列
2.从右往左找递减序列
3.再一个个判断是否满足条件。

我们找到最左端开始递减的位置 ii，有 arr[i-1] > arr[i]arr[i−1]>arr[i]
然后找到最右端开始递增的位置 jj，有 arr[k] <= arr[k+1], k >= jarr[k]<=arr[k+1],k>=j
arr[i:j]arr[i:j] 这一段数组必须删除，而要满足题目条件，我们需要考察 arr[:i] + arr[j:]arr[:i]+arr[j:] 左右两段数组拼在一起是否非递减
只需遍历左边数组的每一个位置，找到右边数组相应的非递减的端点，我们就可以得到答案

代码：

func findLengthOfShortestSubarray(arr []int) int {
    l := 0
    //先找到前缀递增序列
    for l < len(arr) - 1 && arr[l] <= arr[l+1]{
        l ++
    }
    if l == len(arr) - 1{
        return 0
    }
    //再找到后缀递增序列
    r := len(arr) - 1
    for r > 0 && arr[r] >= arr[r-1]{
        r -- 
    }
    //保留前缀序列或后缀序列
    ans := min(len(arr) - l - 1,r)
    //双指针判断
    i := 0
    j := r
    for i <= l && j <= len(arr) - 1{
        if arr[i] <= arr[j]{
            ans = min(ans,j - i - 1)
            i ++
        }else{
            j ++
        }
    }
    return ans
}
func min(a,b int)int{
    if a < b{
        return a
    }
    return b
}

443. 压缩字符串中等

给你一个字符数组 chars ，请使用下述算法压缩：

从一个空字符串 s 开始。对于 chars 中的每组连续重复字符：

如果这一组长度为 1 ，则将字符追加到 s 中。
否则，需要向 s 追加字符，后跟这一组的长度。
压缩后得到的字符串 s 不应该直接返回，需要转储到字符数组 chars 中。需要注意的是，如果组长度为 10 或 10 以上，则在 chars 数组中会被拆分为多个字符。

请在修改完输入数组后，返回该数组的新长度。

你必须设计并实现一个只使用常量额外空间的算法来解决此问题。

示例 1：
输入：chars = [“a”,”a”,”b”,”b”,”c”,”c”,”c”]
输出：返回 6 ，输入数组的前 6 个字符应该是：[“a”,”2”,”b”,”2”,”c”,”3”]
解释：”aa” 被 “a2” 替代。”bb” 被 “b2” 替代。”ccc” 被 “c3” 替代。

示例 2：
输入：chars = [“a”]
输出：返回 1 ，输入数组的前 1 个字符应该是：[“a”]
解释：唯一的组是“a”，它保持未压缩，因为它是一个字符。

示例 3：
输入：chars = [“a”,”b”,”b”,”b”,”b”,”b”,”b”,”b”,”b”,”b”,”b”,”b”,”b”]
输出：返回 4 ，输入数组的前 4 个字符应该是：[“a”,”b”,”1”,”2”]。
解释：由于字符 “a” 不重复，所以不会被压缩。”bbbbbbbbbbbb” 被 “b12” 替代。

提示：
1 <= chars.length <= 2000
chars[i] 可以是小写英文字母、大写英文字母、数字或符号

题解概要：

1.模拟压缩的过程，思路不难，但代码需要考虑很多边界问题，还是比较难写对的。

代码：

func compress(chars []byte) int {
    w, r := 0, 0
    for r < len(chars) {
        rStart := r
        for r+1 < len(chars) && chars[r+1] == chars[r] {
            r++
        }
        chars[w] = chars[rStart]
        w++
        if rStart != r {
            count := r - rStart + 1
            wStart := w
            for count != 0 {
                chars[w] = byte(count%10) + '0'
                w++
                count /= 10
            }
            //翻转
            reverse(chars,wStart,w-1)
        }
        r++
    }
    return w
}
func reverse(chars []byte, l int, r int) {
    for l < r {
        t := chars[l]
        chars[l] = chars[r]
        chars[r] = t
        l++
        r--
    }
}

3. kmp算法

28. 实现 strStr() 简单

实现 strStr() 函数。
给你两个字符串 haystack 和 needle ，请你在 haystack 字符串中找出 needle 字符串出现的第一个位置（下标从 0 开始）。如果不存在，则返回 -1 。

说明：
当 needle 是空字符串时，我们应当返回什么值呢？这是一个在面试中很好的问题。
对于本题而言，当 needle 是空字符串时我们应当返回 0 。这与 C 语言的 strstr() 以及 Java 的 indexOf() 定义相符。

示例 1：
输入：haystack = “hello”, needle = “ll”
输出：2

示例 2：
输入：haystack = “aaaaa”, needle = “bba”
输出：-1

示例 3：
输入：haystack = “”, needle = “”
输出：0

提示：
0 <= haystack.length, needle.length <= 5 * 104
haystack 和 needle 仅由小写英文字符组成

题解概要：

1.本题使用到了kmp算法，关于kmp算法讲解，查看大佬的讲解。
https://programmercarl.com/0028.%E5%AE%9E%E7%8E%B0strStr.html#%E5%85%B6%E4%BB%96%E8%AF%AD%E8%A8%80%E7%89%88%E6%9C%AC

代码：

func strStr(haystack string, needle string) int {
    if len(needle) == 0{
        return 0
    }
    if len(haystack) == 0{
        return -1
    }
    next := make([]int,len(needle))
    getNext(next,needle)
    j := -1
    for i := 0;i < len(haystack);i++{
        for j >= 0 && haystack[i] != needle[j+1]{
            j = next[j]
        }
        if haystack[i] == needle[j+1]{
            j++
        }
        if j == len(needle)-1{
            return i-len(needle)+1
        }
    }
    return -1
}
//实现Next数组
func getNext(next []int,needle string){
    j := -1
    next[0] = j
    for i := 1;i < len(needle);i++{
        for j >= 0 && needle[i] != needle[j+1]{
            j = next[j]
        }
        if needle[i] == needle[j+1]{
            j ++
        }
        next[i] = j
    }
}

1. 双指针简介

2. 双指针相关题目

15. 三数之和 中等

16. 最接近的三数之和 中等

18. 四数之和 中等

80. 删除有序数组中的重复项 II 中等

189. 轮转数组 中等

151. 翻转字符串里的单词 中等

面试题 01.05. 一次编辑 中等

986. 区间列表的交集 中等

658. 找到 K 个最接近的元素 中等

524. 通过删除字母匹配到字典里最长单词 中等

31. 下一个排列 中等

1574. 删除最短的子数组使剩余数组有序 中等

443. 压缩字符串 中等

3. kmp算法

28. 实现 strStr() 简单

15. 三数之和中等

16. 最接近的三数之和中等

18. 四数之和中等

189. 轮转数组中等

151. 翻转字符串里的单词中等

面试题 01.05. 一次编辑中等

986. 区间列表的交集中等

658. 找到 K 个最接近的元素中等

524. 通过删除字母匹配到字典里最长单词中等

31. 下一个排列中等

1574. 删除最短的子数组使剩余数组有序中等

443. 压缩字符串中等