算法-指针相关

滑动窗口 就是 双指针

相向双指针

leetcode 167.两数之和 –> 进阶变形 15.三数之和

1. 一个指针指向数组最左，一个指针指向数组最右
2. 一般来说数组需要从小到大排序
3. 默认左指针一定会小于右指针
4. 左指针+右指针之和小于目标值，左指针加 1，否则右指针减 1

前缀和

leetcode 3096

1. 一般来说，按顺序求和，分为两个子数组
2. 指针只改变一个

滑动窗口

leetcode 209、713、3

1. 一般来说两个循环+一个指针或者说两个指针也可以，第二个指针包含在外部循环里
2. 两个指针方向要一致，从 0 开始，就都从 0 开始，外部循环是外部指针跟随每次遍历而动，内部循环是满足条件后，第二指针改变
3. 一般来说第二指针会比第一指针慢，两个指针可以相等，但要看条件是什么，如果求长度+1，能保证最小长度为 1

• 模板

  let L = 0
  let sum = 0
  let len = 0
  for(let R =0,R<arr.length;R++){
  	sum += arr[R] // 位置可变，或先内循环在计算
  	while(sum < target) { // 条件可变
  		len = Math.max(len, R-L+1) // 位置可变，或外循环
  		sum -= arr[L]
  		L++
  	}
  }
  return len

二分查找的基础知识

leetcode 34. 在排序数组中查找元素的第一个和最后一个位置
leetcode 不是有序的数组也能使用二分查找。162 也算跳跃窗口

• 三种解法，适用 >=target

  • 如果是 >target 的话，把它看成 x>=target+1
  • 如果是 <target 的话，把它看成 (x>=target)-1
  • 如果是 <=target 的话，把它看成 (x>target)-1

• 模板

1. 闭区间解法

   const fn = (nums:number[],targrt:number): number => {
   	let left = 0
   	let right = nums.length - 1 // 闭区间【left，right】
   	while left <= right: // 区间不为空
   		let mid = Math.floor((L+R)/2)
   		if (nums[mid] < target) left = mid + 1 // [mid+1, right]
   		else right = mid -1 // [left, mid-1]
   	return left
   }

2. 左闭右开区间解法

   const fn = (nums: number[], target: number): number => {
   	let left = 0
   	let right = nums.length // 左闭右开区间【left，right)
   	while left < right: // 区间不为空
   		let mid = Math.floor((L+R)/2)
   		if (nums[mid] < target) left = mid +1 // [mid+1, right)
   		else right = mid // [left, mid)
   	return left
   }

3. 开区间解法

   const fn = (nums: number[], target: number): number => {
   	let left = -1
   	let right = nums.length // 开区间(left，right)
   	while left + 1 < right: // 区间不为空
   		let mid = Math.floor((L+R)/2)
   		if (nums[mid] < target) left = mid  // (mid+1, right)
   		else right = mid // (left, mid)
   	return right
   }

旋转排序数组

leetcode 162.寻找峰值,153.寻找旋转排序数组中的最小值，33.搜索旋转排序数组

• 模板

  let L = -1
  let R = arr.length - 1
  
  while (L + 1 < R) {
  	let mid = Math.floor((L + R) / 2)
  	if (arr[mid] < arr[arr.length - 1]) {
  		// 条件可改
  		L = mid
  	} else {
  		R = mid
  	}
  }
  
  return nums[R] // 结果可改

单调栈(pop)

leetcode 739

• 利用栈的特性：后进先出

1. 先初始化数组
2. 每次判断临时数组数组长度大于 0 并且当前元素大于等于栈中的最后一个元素对应在数组中的元素，如果有这个情况临时数组就出栈
3. 如果临时数组经过出栈后仍然保留则向对应位置的初始化数组添加元素
4. 每次都先向临时数组中添加当前元素的索引
5. 最后返回初始化数组