这是算法记录的第一天，主要包含快慢指针技巧
数组之双指针
算法之旅从数组开始，今天从三道题目基本掌握了快慢指针的技巧
27.移除元素
给你一个数组nums和一个值val，你需要原地移除所有数值等于val的元素，并返回移除后数组的新长度。
不要使用额外的数组空间，你必须仅使用 O(1) 额外空间并原地修改输入数组。
元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。
示例 1:
输入：nums = [3,2,2,3], val = 3
输出：2, nums = [2,2]
解释：函数应该返回新的长度 2, 并且 nums 中的前两个元素均为 2。你不需要考虑数组中超出新长度后面的元素。例如，函数返回的新长度为 2 ，而 nums = [2,2,3,3] 或 nums = [2,2,0,0]，也会被视作正确答案。
示例 2:
输入：nums = [0,1,2,2,3,0,4,2], val = 2
输出：5, nums = [0,1,4,0,3]
解释：函数应该返回新的长度 5, 并且 nums 中的前五个元素为 0, 1, 3, 0, 4。注意这五个元素可为任意顺序。你不需要考虑数组中超出新长度后面的元素。
你不需要考虑数组中超出新长度后面的元素。
暴力解法
思路：一层for循环遍历数组，找到目标值就用另一层for循环更新数组（剩下都往前移动一位）
正如名字，时间复杂度是O(n^2)
func removeElement(nums []int, val int) int {
length := len(nums)
for i := 0; i < length; i++ {
if nums[i] == val {
for j := i + 1; j < length; j++ {
nums[j-1] = nums[j] //避免数组越界，先+1再-1确保还是i
}
i-- //向前移动一位，确保比较的是移除元素前的i+1（相当于i和数组同步左移一位）
length-- //移除一个元素，数组长度减一
}
}
return length
}
快慢指针
思路：若fast遇到val就跳过，否则就把fast赋值给slow，并让slow前进一步
- 快指针：遇到
val跳过，不断寻找新数组的非val元素 - 慢指针：指向新数组的下标
这样保证了nums[0, slow-1]里面没有目标val值，当fast遍历完后也就得到最后结果nums[0,slow-1]（返回的是数组长度slow）
func removeElementWithPoints(nums []int, val int) int {
slow := 0
for fast := 0; fast < len(nums); fast++ {
if nums[fast] != val {
nums[slow] = nums[fast] //需要保证nums中不包含val，所以需要覆盖当前的值
slow++
}
}
return slow //直接返回的就是剩下的数组，当前slow指向的不在里面
}
26.删除有序数组重复元素
给你一个升序排列的数组 nums ，请你 原地 删除重复出现的元素，使每个元素只出现一次 ，返回删除后数组的新长度。元素的相对顺序应该保持一致 。
将最终结果插入 nums 的前 k 个位置后返回 k 。
不要使用额外的空间，你必须在 原地修改输入数组 并在使用 O(1) 额外空间的条件下完成。
示例 1：
输入：nums = [1,1,2]
输出：2, nums = [1,2,_]
解释：函数应该返回新的长度 2 ，并且原数组 nums 的前两个元素被修改为 1, 2 。不需要考虑数组中超出新长度后面的元素。
示例 2：
输入：nums = [0,0,1,1,1,2,2,3,3,4]
输出：5, nums = [0,1,2,3,4]
解释：函数应该返回新的长度 5 ， 并且原数组 nums 的前五个元素被修改为 0, 1, 2, 3, 4 。不需要考虑数组中超出新长度后面的元素。
快慢指针
和27非常相似，慢指针slow在后面，快指针fast走在前面寻找不重复元素，当找到一个不重复的元素就赋值给slow并让slow前进一步。
这样保证了nums[0, slow]里面都是不重复的元素，当fast指针遍历完整个数组nums后，nums[0, slow]就是整个数组去重之后的结果。
func removeDuplicates(nums []int) int {
slow := 0
for fast := 0; fast < len(nums); fast++ {
//无视重复的
if nums[fast] != nums[slow] {
//slow指向的是结果数组，有新加的就向后移动
slow++
nums[slow] = nums[fast]
}
}
return slow + 1
}
这里和27的移除元素有一个细节不同，这里是先slow++再给nums[slow]赋值，确保当前重复的元素（slow）会保留下来，去除的是重复元素（一个是删除，一个是去重）
283.移动零
给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。
请注意 ，必须在不复制数组的情况下原地对数组进行操作。
示例 1:
输入: nums = [0,1,0,3,12]
输出: [1,3,12,0,0]
示例 2:
输入: nums = [0]
输出: [0]
快慢指针
这个就和移除元素完全一样了，只需要最后的再赋0值就行了
func moveZeroes(nums []int) {
slow := 0
for fast := 0; fast < len(nums); fast++ {
if nums[fast] != 0 {
nums[slow] = nums[fast]
slow++
}
}
for i := slow; i < len(nums); i++ {
nums[i] = 0
}
}
总结
关键点在于：
- 要保留的是哪个值
- 慢指针+1和赋值的相互位置
- 返回的slow是什么
Tip
- go语言中切片是引用类型，数组是值类型，所以需要传递切片才会修改