算法
双指针
leetcode100双指针
移动零
有关数组题,大概率用双指针写 这个典型要找到一个是0,一个不是0的数。先试试快慢指针 slow指针可以代表什么?第一个零的位置?下一个非零元素放的位置? fast指针可以代表什么?遍历一下看到第一个不是零的元素
let slow,fast=0
for(fast<nums.length;fast++)
if(nums[fast]!==0){
[nums[fast],nums[slow]]=[[nums[slow],nums[fast]]]
slow++
}如果f,s为0,f++,把s留在原地,如果f不为0且s也不为0,那就一起++,如果f不为0,s为0,那就说明找到了,交换
三数之和
就是一个外层循环,内层while(l<r)
然后注意去重,当计算l+r+i===taregt的时候。先push进结果,然后
while(l<r&&nums[l]===nums[l+1])l++,
while(l<r&&nums[r]===nums[r-1])r--,最后一定还要l++,r--
接雨水
核心思路就是给height左右两边添加0作为边界,然后一次计算两个边界里面的盛水量。 从左到右
let l,sum=0
//r是快指针,用来判断height[r]>=height[l]的,如果大于,说明两个边界中可以装水
for(let r=0;r<height.length;r++){
if(height[r]>=height[l]){
res += h[l] * (r - l - 1) - sum;//计算当前水量
l=r//更新l
sum=0//重置
}else{
sum++height[r]//这个容器中间会有其他占位
}
//当中间碰到最高,也就是height[l]最大了
r=height.length-1
sum=0
for(let i=r;i>=l;i--){
res+=xxx
r=i
sum=0
}else{
sum+=height[i]
}
}