本文hot100双指针解法
移动零
解法1：把nums当成栈
直接把 nums 当作栈，用一个变量 stackSize 表示栈的大小，初始值为 0。
入栈就是把 nums[stackSize] 置为 nums[i]，然后把 stackSize 加一。
最后把 nums 中的下标从 stackSize 到 n−1 的数都置为 0。
func moveZeroes(nums []int) {
stackSize := 0
for _ , x := range nums {
if x != 0{
nums[stackSize] = x
stackSize++
}
}
clear(nums[stackSize:]) //stackSize后的置为0
}
解法2：双指针
其实就是用i0去记录非0的放置位置，枚举nums，如果是非0，就在nums[i0]放置nums[i]（x），而nums[i]就为0，进行类似位置交换
func moveZeroes(nums []int) {
i0 := 0 //非0的放置位置
for i ,x := range nums{
if x!=0 {
nums[i] = 0
nums[i0] = x
i0++
}
}
}
盛最多水的容器
这题的最优解法就是双指针
直接left right 向中间靠，哪边的height小，哪边往中间靠拢
func maxArea(height []int) (ans int) {
left , right := 0 , len(height)-1
for left<right {
s := (right-left)* min(height[left],height[right])
ans = max(s,ans)
if height[left]<height[right] {
left++
} else {
right–
}
}
return
}
三数之和
这个题也是双指针，就是把问题拆解为排序完后，在i–n中，nums[j]+nums[k]=nums[i]的二元组，只需要注意不重复
func threeSum(nums []int) (ans[][]int) {
slices.Sort(nums)
n := len(nums)
for i , x := range nums[:n-2]{
if i >0 && x== nums[i-1]{
continue
}
if x+ nums[i+1]+nums[i+2]>0{
break
}
if x+nums[n-2]+nums[n-1]<0{
continue
}
j,k := i+1,n-1
for j < k {
s := x + nums[j] + nums [k]
if s>0 {
k–
} else if s<0 {
j++
} else {
ans = append(ans, []int{x,nums[j],nums[k]})
for j++; j < k && nums[j] == nums[j-1]; j++ {} // 跳过重复数字
for k–; k > j && nums[k] == nums[k+1]; k– {}
}
}
}
return
}
接雨水
这题方法挺多种，但我就只记录双指针,代码处即为分析
func trap(height []int) (ans int) {
//双指针，这题思路为双指针相向
//可以分析left和right位置的接水量是由其那边的最高决定的（左边需要由它左边最高，右边同理）
//即 height[n] – Max 为n这个位置的接水单位（Max为靠那边的最高位）
//当然由于整个数组中柱子最高是一定不能接水的，而且上面的接水单位计算不能够有最高位参与，也就是最高位为中心点
leftMax, rightMax := 0, 0
left, right := 0, len(height)-1
for left < right {
leftMax = max (leftMax , height[left])
rightMax = max (rightMax,height[right])
if leftMax < rightMax{
ans += leftMax -height[left]
left++
} else {
ans += rightMax-height[right]
right–
}
}
return
}
