数组

704 二分查找

从始至终遵循同一个数组边界定义，左闭右开 | 左闭右闭

69. X 的平方根

题目只要求整数精度，问题演化为找到一个最大 ans 使得 ans * ans < X 且 (ans + 1) * (ans + 1) > X

初始化边界为 [0, x]
不断二分迭代，找到 ans

27 移除元素

关键点 对快慢指针的理解：快指针 -- 查找，哨兵慢指针 -- 实际赋值处，操作结果数组

977 有序数组的平方

关键点 题目的特殊性，升序排列，有负数的话，那平方最大的数字肯定是从两端到中间逼近的。所以可以通过双指针向中间逼近，一步步获取最大值、次大值......

$209 长度最小的子数组 | 滑动窗口

关键点 两重循环的话不用说，外循环起点，内循环终点，遍历所有可能的情况滑动窗口是关键，题目中，说明了数组中每个元素都是正整数，所以带来了某些隐藏条件，就比如，起点终点之间的元素和总是窗口越宽越大，因为加的都是正整数，所以就可以用滑动窗口的思想

移动窗口的右侧（终点指针）
如果满足条件，再尝试移动窗口的左侧（起点指针）一直移动找到该终点指针下的最小窗口宽度。
重复（1）（2）

$59 螺旋矩阵

循环不变量：

每次都是处理一圈，从外圈一点点到内圈。
每一圈都是处理四条边，每条边都是处理0到末尾前一个。
利用offset来控制每一圈的偏移量。

66. 加一

描述：一个数组，表示一个大整数，加一，返回加一后的数组
实现：
- 取个位，若<9，个位加一返回
- 考虑进位，可以提前unshift一个0，倒着遍历，实现进位
- 最后返回的时候有必要的话把第一个0去掉

724. 寻找数组的中心下标

描述：求一个下标I，使得[0-I-1]的和等于[I+1-n]的和
实现：
- 初始化I为0，left=0,right = sum - nums[0]
- 向右遍历，left += nums[I],right -= nums[I+1]

189. 轮转数组

描述：把一个数组，向右轮转k个位置，有点像环形链表的感觉
实现：
- 整个数组翻转，后面的就到前面了
- 翻转前k个，轮转的K个就对了
- 翻转后n-k个
注意：
- 当k>n时，k=k%n

48. 旋转图像

描述：把一个N*N矩阵，顺时针旋转90度
实现：
- 元素(i,j)的旋转规律为(i,j) -> (j,n-i-1)
- 在一圈的元素中，遍历一行的n-1个元素，然后进行循环交换 a->b->c->d->a
  - (i,j) -> (j,n-i-1), 同样的, 通过代入可得，(j,n-i-1) -> (n-i-1,n-j-1)....
注意：
- 一层一层的向内旋转，那么外层遍历层数为n/2 | 0
- 每一层遍历的元素为level, n-level-1

54. 螺旋矩阵

描述：给定一个m*n的矩阵，按照顺时针螺旋顺序遍历，返回矩阵中的所有元素
实现：
- 一层层遍历，外层循环遍历层，层数 = min(m,n) / 2 | 0
- 循环体内部分别处理四条边，注意左闭右开
- top: 从左到右遍历列[layer, n-layer-1)
- right: 从上到下遍历行[layer, m-layer-1)
- bottom: 从右到左遍历列[n-layer-1, layer)
- left: 从下到上遍历行[m-layer-1, layer)
注意处理奇数边，容易遗漏
- if min(m,n) % 2 === 1 或 layerNum === 0
- 可能是剩下单独一行 [layer, n-layer)
- 可能是剩下单独一列 [layer, m-layer)

498. 对角线遍历

描述：给定一个m*n的矩阵，按照对角线顺序遍历，返回矩阵中的所有元素
实现：
- 不要想着按层或者按条去遍历，而是从[0,0]开始，走一步看一步
- 规律：i+j 为偶数时，向右上走，i+j 为奇数时，向左下走
注意：
- 边界比较多，往右上走时，需要考虑在第一行，在最后一列的情况
- 往左下走时，需要考虑在最后一行，在第一列的情况

快速排序

时不时得写一下，容易忘记
要点：
- 一个核心函数：实现pivot前面的都小于pivot，pivot后面的都大于pivot，返回pivot的index
  - 我习惯于取第一个元素为pivot
  - 从后往前遍历j，>=时，j--，找到第一个小于pivot的元素
  - 然后从前往后遍历i, <=时，i++，找到第一个大于pivot的元素
  - 交换i和j的元素
  - 最后i和j相遇跳出循环，把arr[0]和arr[i]交换。
- 一个调度函数：递归调用，基于pivot的index，递归自调用

167. 两数之和II

描述：给定一个升序数组，找到两个数，使得它们相加之和等于目标数
实现：
- 双指针，一个从左到右，一个从右到左
- 因为是升序的了，sum > target 时，右指针左移，sum < target 时，左指针右移
注意：
- 返回的下标需要 + 1

125. 验证回文串

描述：给定一个字符串，去除非字母数字的字符，大写转小写，判断它是否是回文串
注意：
- 记得字符串大小写转换 toLowerCase() toUpperCase()

11. 盛最多水的容器

描述：给定一个height数组，height[i]和height[j]组成一个容器，求容器中能盛最大容量
实现：
- 容量：(j-i) * min(height[i], height[j])
- 用一个变量记录最大容量，在遍历过程中更新
- 对撞指针，移动高度小的指针，让拖后腿的加把劲
- 面积 = 两个指针的距离 * 两个指针中较小的值
- 移动指针，移动较小的值的指针

26. 删除有序数组中的重复项

描述：给定一个非递减数组，删除重复项，返回新的长度
实现：
- 快慢指针，快指针遍历，慢指针记录非重复项
- 快指针遍历到非重复项，慢指针就赋值

1343. 大小为K且平均值大于等于阈值的子数组数目

描述：给定一个数组和一个阈值，求长度为K，且平均值>=阈值的子数组数目

实现：

子序列问题，考虑滑动窗口实现，不用记录元素，只需要记录窗口内元素的和
这个结构特别好，很清晰

  let left = 0, right = 0
  while(right < arr.length) {
    window.push(arr[right])
    
    if(right - left + 1 > windowSize){ // 定长窗口
      
      // 维护和更新求解的答案...

      window.shift()
      left++
    }

    right++
  }

3. 无重复字符的最长子串

描述：求一个字符串中，不含重复字符的最长子串的长度
实现：
- 子串问题，滑动窗口实现，这题的核心是不含重复元素的判断
- 可以用数组，每次用indexOf判断
- 可以用Map, Set, 每次用has判断, 因为不需要放什么值，所以用Set即可
txt
```
  1. 考虑塞入s[right], 先清理再塞入，清理的时候就是窗口收缩
  2. 考虑求解目标，维护ans
  3. right ++
```

215. 数组中的第K个最大元素

描述：给一个数组，求数组中第K大的元素
注意：本题测试案例贼TM搞，第41是一个包含几万个重复元素的，导致常规的快速选择二路划分会超时

快速选择实现

超时版：虽然pivot是随机选的，但是当数组中元素大部分相同时，会退化成O(n^2)

 function qkSelect(nums, left, right, targetIndex) {
     if (left == right) return nums[left] 
     const randomIndex = Math.floor(Math.random() * (right - left + 1)) + left;
     [nums[left], nums[randomIndex]] = [nums[randomIndex], nums[left]]
     const pivot = nums[left]
     let i = left, j = right  
     while (i < j) {
         // 前小后大
         while (i < j && nums[j] >= pivot) j--
         while (i < j && nums[i] <= pivot) i++  
         if (i < j) [nums[i], nums[j]] = [nums[j], nums[i]]
     }
     nums[left] = nums[i]
     nums[i] = pivot  
     if (targetIndex == i) return nums[targetIndex]
     if (targetIndex > i) return qkSelect(nums, i + 1, right, targetIndex)
     else return qkSelect(nums, left, i - 1, targetIndex)
 }

优化版: 三路划分[小于pivot, 等于pivot, 大于pivot]三个区间

  function qkSelect(nums, left, right, targetIndex) {
    if (left >= right) return nums[left]

    const pivot = nums[left]

    // 三路划分
    // 此时 [left, lt) < pivot, [lt, gt] == pivot, (gt, right] > pivot
    let lt = left, gt = right, i = left + 1

    while (i <= gt) {
        if (nums[i] < pivot) {
            [nums[i], nums[lt]] = [nums[lt], nums[i]]
            lt++
            i++
        } else if (nums[i] > pivot) {
            [nums[i], nums[gt]] = [nums[gt], nums[i]]
            gt--
        } else {
            i++
        }
    }

    // 判断 targetIndex 是否落在等于区
    if (targetIndex >= lt && targetIndex <= gt) {
        return nums[targetIndex]
    } else if (targetIndex < lt) {
        return qkSelect(nums, left, lt - 1, targetIndex)
    } else {
        return qkSelect(nums, gt + 1, right, targetIndex)
    }
  }

堆排序实现

建一个小顶堆，可以维护一个大小为k的小顶堆
建堆时，如有空间，就直接入堆
如果无空间，判断当前元素是否大于堆顶，大于就pop堆顶，然后入堆
最后，整个堆就是整个数组中前k个最大的，堆顶就是第k大的元素
注意，把小顶堆写成一个类是最舒服的，核心函数_up和_down，写成递归的最舒服
注意, 维护一个k的小顶堆, 是在外部建堆的时候做的事情。

  class MinHeap {

      constructor() {
          this.heap = []
      }

      _up(id) {
          if (id == 0) return

          const fatherId = (id - 1) / 2 | 0
          if (this.heap[fatherId] > this.heap[id]) {
              // swap and up
              [this.heap[fatherId], this.heap[id]]
                  = [this.heap[id], this.heap[fatherId]]

              this._up(fatherId)
          }

      }

      _down(id) {
          if (id >= this.heap.length) return

          let leftID = id * 2 + 1
          let rightID = id * 2 + 2
          let smallestID = id

          if (leftID < this.heap.length && this.heap[smallestID] > this.heap[leftID]) {
              smallestID = leftID
          }
          if (rightID < this.heap.length && this.heap[smallestID] > this.heap[rightID]) {
              smallestID = rightID
          }

          if (smallestID != id) {
              // swap and down
              [this.heap[smallestID], this.heap[id]]
                  = [this.heap[id], this.heap[smallestID]]

              this._down(smallestID)
          }

      }

      peek() {
          return this.heap[0]
      }

      insert(num) {
          this.heap.push(num)
          this._up(this.heap.length - 1)
      }

      shift() {
          if (this.heap.length == 0) return null
          if (this.heap.length == 1) return this.heap.pop()

          const res = this.heap[0]
          const last = this.heap.pop()
          this.heap[0] = last

          this._down(0)
          return res
      }

  }

  var findKthLargest = function (nums, k) {

      const minHeap = new MinHeap()

      for (let num of nums) {
          if (minHeap.heap.length < k) minHeap.insert(num)
          else if (num > minHeap.peek()) {
            // 这里是重点，只有当当前num比堆顶大的时候，才入堆
            // 这样最终我们的堆里才是最大的k个数
              minHeap.shift()
              minHeap.insert(num)
          }
      }

      return minHeap.peek()
  };

==复杂度分析==

仅对前K个元素建堆（小顶堆，用于找前K大元素）。此时建堆的复杂度为O(K)（向下调整建堆的时间复杂度与堆的大小K相关）。

随后遍历剩余的N-K个元素，若元素大于堆顶（当前第K大元素），则替换堆顶并调整堆，每次调整的时间复杂度为O(logK)。

总时间复杂度为O(K + (N-K)logK)，当N远大于K时，可近似为O(NlogK)。

33. 搜索旋转排序数组

方法一：效率低 先找 k 再二分查找

// find k
let k = 1
while (k < nums.length && nums[k] > nums[k - 1]) k++

const bSearch = (arr, left, right, target) => {
	if (left > right) return -1
	const mid = (left + right) / 2 | 0
	if (arr[mid] === target) return mid
	else if (arr[mid] > target) return bSearch(arr, left, mid - 1, target)
	else return bSearch(arr, mid + 1, right, target)
}

// two part search
const a = bSearch(nums, 0, k - 1, target)
const b = bSearch(nums, k, nums.length - 1, target)

方法二：直接二分查找，二分地缩小区间

计算 mid
（直接找到 target 的话，提前返回）
如果左侧有序
- 如果 target 在左侧，即 nums[left] < target < nums[mid]，那在左侧找
- 否则在右侧
如果右侧有序
- 如果target 在右侧，即 nums[mid] < target < nums[right]，那在右侧找
- 否则在左侧

88. 合并两个有序数组

方法一：开辟新数组，双指针同时遍历两个数组，填入新数组

方法二：原地合并，因为 num1 的后半部分是空的，所以从后半部分往前填充，逆向的双指针，注意 m=0 和 n=0 情况的处理

// 原地法
let tail = m + n - 1
let i = m - 1; j = n - 1 // 指向未确定部分的最大值
while (i >= 0 || j >= 0) {
	// 这样就很清晰，处理了各种情况
	let selected
	if (i == -1) {
		selected = nums2[j--]
	} else if (j == -1) {
		selected = nums1[i--]
	} else if (nums1[i] > nums2[j]) {
		selected = nums1[i--]
	} else {
		selected = nums2[j--]
	}
	nums1[tail--] = selected
}

56. 合并区间

思路：排序然后用栈实现，栈顶元素是当前的范围。处理 [1,4], [2,3] 和 [1,4], [2,5] 两种情况即可。

42. 接雨水

思路： 每一列可以装的水量 = Max(Min(左边最高，右边最高) - 该列高度 , 0) 实现：

构造一个leftMax和rightMax数组，省得每次都遍历找。
用上面的公式即可求解

22. 括号生成

方法一：回溯产生所有可能的组合 + 遍历 valid 判断

// 可能的组合
let leftNum = n, rightNum = n
let possible = []
let cur = []
function genPossible(startId) {
	if (startId === 2 * n) {
		possible.push(cur.join(''))
		return
	}
	if (leftNum > 0) {
		cur.push('(')
		leftNum--
		genPossible(startId + 1)
		// 回溯
		leftNum++
		cur.pop()
	}
	if (rightNum > 0) {
		cur.push(')')
		rightNum--
		genPossible(startId + 1)
		// 回溯
		rightNum++
		cur.pop()
	}
}
genPossible(0)

方法二：一次回溯，在回溯过程中考虑有效的括号,核心是：只有当前路径中，左括号数目比右括号数目多，才应该插入右括号，等于都不行！必须大于！

let leftNum = n, rightNum = n // 可用的左括号数量和右括号数量
function backTrack(startID) {
	if (startID === 2 * n) {
		ans.push(cur.join(''))
		return
	}

	if (leftNum > 0) { // 左括号只要有就能放
		leftNum--
		cur.push('(')
		backTrack(startID + 1)
		cur.pop()
		leftNum++
	}

	if (rightNum > 0 && rightNum > leftNum) { // 如果cur里边左括号多，即剩余的右括号更多，那么可以插入
		rightNum--
		cur.push(')')
		backTrack(startID + 1)
		cur.pop()
		rightNum++
	}
}

31. 下一个排列

求整数数组的下一个字典序稍微更大的排列，如果已经是最大，返回最小.

txt

123 --> 132 --> 213 --> 231 --> 312 --> 321 --> 123

123456 --> 123465 --> 123546 --> 123564 --> ...

究极找规律型题目，要让他字典序稍微更大一点，这里的整数数组可以看作一个整数，那就是稍大一点的整数。要稍大一点，那么肯定是尽可能从数字的低位（右边）操作好一些。

直接给家人们上规律

txt

1. 从右往左找第一个*相邻*升序 nums[i] < nums[j], i + 1 === j
2. 如果找到了 i，j, 此时[j,end]必定是一个降序序列，在这个区间里边找到 nums[k](nums[i] 的最小的整数)
3. 交换 nums[k] nums[j] 这俩最小的大数和最大的小数
4. 使 [j,end] 升序排列

---- 

例子：求 123465 的下一个排列
1. 找到相邻升序 4 < 6 
2. 再在 6 及其之后的区间里找到最小的大数 5
3. 交换,得到 123564
4. 让 6 及其之后的区间升序排列，得到 123546

    if (nums.length <= 1) return

    // 1.从后往前找升序的元素对
    let i = nums.length - 2
    let j = nums.length - 1
    let k = nums.length - 1
    while (i >= 0 && nums[i] >= nums[j]) {
        i--
        j--
    }

    // 2.在[j,end]这个降序区间，找尽可能小的大数
    if (i >= 0) { // 不是最后一个排列
        while (nums[i] >= nums[k]) {
            k--
        }
        // 此时 nums[k] > nums[i], 一个是最小的大数，一个是最大的小数
        [nums[k], nums[i]] = [nums[i], nums[k]]
    }

    // 3.使降序的[j,end] 升序
    let L = j, R = nums.length - 1
    while (L < R) {
        [nums[R], nums[L]] = [nums[L], nums[R]]
        R--
        L++
    }

162. 寻找峰值

找一个序列里的峰值，这个峰值元素比旁边俩大即可，不需要是最大值。

思路：二分搜索法：利用局部上升或下降的趋势缩小查找范围。如果 nums[mid] > nums[mid+1]，这是一个局部下降的趋势，那么峰值肯定出现在 mid 本身或 mid 左边。如果nums[mid] < nums[mid+1]，一个上升趋势，那么峰值肯定出现在 mid + 1或者更靠后

560. 和为 K 的子数组

给你一个整数数组 nums 和一个整数 k ，请你统计并返回该数组中和为 k 的子数组的个数。子数组是数组中元素的连续非空序列。

思路： 最直观的：枚举子串 O n方，确定起点，然后遍历终点的同时加和判断

优化：

首先是理解前缀和

txt

prefix[i] : 索引为0到i-1的这个子数组的元素的和。

如果我们要求索引 i 到 j 的子数组的元素和，就可以用上它：
sum<i,j> = prefix[j + 1] - prefix[i] // 即 sum<0,j> - sum<0,i-1>

回归题目, 我们要找和为 k 的子数组有多少个

找 k === prefix[j + 1] - prefix[i] 的 ij 有多少种先遍历建 prefix 然后再 for i , for j 找？？

no, 那就又变成 n方了

记忆化

对于 prefix[i] 我想知道 k - prefix[j + 1] 有没有？如果能那个表记下来就好了。

所以每次遇到 prefixSum 就记录下来，计数 + 1，这个表的key就是prefixSum，value是count

所以：

function solve(nums){

	let map = new Map()
	map.set(0, 1) // 初始化，处理从0开始的子数组，我们记录为0出现过一次

	let res = 0
	let cursum = 0
	for(const num of nums){
		cursum += num
		// 注意这里
		if(map.has(cursum - k)){
	// 如果能找到 前缀和为 cursum -k 的，那俩序列一减就得到了一个目标子序列
			res += map.get(k-cursum)
		}
		// 记录当前的
		map.set(cursum, (map.get(cursum) || 0) + 1)
	}
}

为什么是 cursum - k 设我们要找的前缀和是 P ，我们是从前往后处理的，P 应该是之前出现过的才构成合法子序列，所以有关系 cursum - P = k ，那么 P = cursum - k

数组 ​

704 二分查找 ​

69. X 的平方根 ​

27 移除元素 ​

977 有序数组的平方 ​

$209 长度最小的子数组 | 滑动窗口 ​

$59 螺旋矩阵 ​

66. 加一 ​

724. 寻找数组的中心下标 ​

189. 轮转数组 ​

48. 旋转图像 ​

54. 螺旋矩阵 ​

498. 对角线遍历 ​

快速排序 ​

167. 两数之和II ​

125. 验证回文串 ​

11. 盛最多水的容器 ​

26. 删除有序数组中的重复项 ​

1343. 大小为K且平均值大于等于阈值的子数组数目 ​

3. 无重复字符的最长子串 ​

215. 数组中的第K个最大元素 ​

33. 搜索旋转排序数组 ​

88. 合并两个有序数组 ​

56. 合并区间 ​

42. 接雨水 ​

22. 括号生成 ​

31. 下一个排列 ​

162. 寻找峰值 ​

560. 和为 K 的子数组 ​

数组