数组与双指针

题干：给定 n 条垂直线段，找两条线使得围成的水最多。

• 关键：无论怎么移动长板，面积都不可能更大（宽变小，高受限于短板）→ 所以移动短板

var maxArea = function(height) {
  let max = 0
  let i = 0
  let j = height.length - 1
  while (i < j) {
    let lh = height[i]
    let rh = height[j]
    if (lh < rh) {
      max = Math.max(max, lh * (j - i))
      i++ // 移动短板
    } else {
      max = Math.max(max, rh * (j - i))
      j--
    }
  }
  return max
}

题干：找出数组中所有和为 0 的三元组，不能重复。

• 先排序，固定 k，双指针 i/j 从两端逼近
• 去重：跳过相同值的 k、i、j
• 当 nums[k] > 0 时直接 break（后面不可能为 0）

var threeSum = function(nums) {
  if (nums.length < 3) return []
  const ans = []
  nums.sort((a, b) => a - b)
  let k = 0
  while (k < nums.length - 2) {
    let nk = nums[k]
    if (nk > 0) break // 剪枝
    let i = k + 1
    let j = nums.length - 1
    while (i < j) {
      let ni = nums[i], nj = nums[j]
      if (nk + ni + nj < 0) {
        i++
        while (nums[i] === nums[i - 1]) i++ // 跳重复
      } else if (nk + ni + nj > 0) {
        j--
        while (nums[j] === nums[j + 1]) j--
      } else {
        ans.push([nk, ni, nj])
        i++
        while (nums[i] === nums[i - 1]) i++
        j--
        while (nums[j] === nums[j + 1]) j--
      }
    }
    k++
    while (nums[k] === nums[k - 1]) k++ // 跳重复
  }
  return ans
}

题干：原地删除有序数组中的重复元素，返回新长度。

// 心里想的数组：[1,2,2,2,2,3,4]
var removeDuplicates = function(nums) {
  let i = 0 // 指向已排好的末尾
  let j = 1
  while (j < nums.length) {
    if (nums[j] !== nums[i]) {
      i++
      nums[i] = nums[j] // 不同就往前覆盖
    }
    j++
  }
  return i + 1
}

题干：旋转排序数组（如 [4,5,6,7,0,1,2]）中搜索 target，要求 O(log n)。

• 每次二分，左半或右半至少有一边是有序的
• 判断 target 在有序的那半边还是无序的那半边

var search = function (nums, target) {
  let l = 0, r = nums.length - 1
  let mid = Math.floor(r / 2)
  while (l <= r) {
    if (nums[mid] === target) return mid
    // 左边有序
    if (l <= mid - 1 && nums[l] <= nums[mid - 1]) {
      if (target >= nums[l] && target <= nums[mid - 1]) {
        r = mid - 1 // target 在有序左半边
      } else {
        l = mid + 1
      }
    } else { // 右边有序
      if (target >= nums[mid + 1] && target <= nums[r]) {
        l = mid + 1
      } else {
        r = mid - 1
      }
    }
    mid = Math.floor((l + r) / 2)
  }
  return -1
}

题干：将 n×n 矩阵顺时针旋转 90 度，原地修改。

• 递推公式：(x,y) → (y, n-1-x)
• 分区旋转，奇偶两种情况统一处理

var rotate = function(matrix) {
  const n = matrix.length
  for (let i = 0; i < Math.floor(n / 2); i++) {
    for (let j = 0; j < Math.floor((n + 1) / 2); j++) {
      // 四个位置一轮换
      const temp = matrix[i][j]
      matrix[i][j] = matrix[n - j - 1][i]
      matrix[n - j - 1][i] = matrix[n - i - 1][n - j - 1]
      matrix[n - i - 1][n - j - 1] = matrix[j][n - i - 1]
      matrix[j][n - i - 1] = temp
    }
  }
}

题干：给定区间数组，合并所有重叠的区间。

• 先按左区间排序
• 比较前一个右端点和后一个左端点：能合并就取右端点大者，不能合并就推入结果

var merge = function(intervals) {
  intervals.sort((a, b) => a[0] - b[0])
  let compareArr = []
  let ansArr = []
  for (let i = 0; i < intervals.length; i++) {
    let item = intervals[i]
    if (!compareArr.length) {
      compareArr = item.slice()
    } else if (compareArr[1] < item[0]) { // 无法合并
      ansArr.push(compareArr.slice())
      compareArr = item.slice()
    } else { // 可以合并
      compareArr = [compareArr[0], Math.max(compareArr[1], item[1])]
    }
  }
  if (compareArr.length) ansArr.push(compareArr.slice())
  return ansArr
}

题干：只含 0/1/2 的数组，原地排序（荷兰国旗问题）。

var sortColors = function(nums) {
  let i = 0 // 0 的边界
  let j = 0 // 1 的边界
  for (let k = 0; k < nums.length; k++) {
    let num = nums[k]
    if (num === 0) {
      nums[j] = 1  // 先刷 1
      nums[i] = 0  // 再刷 0（可能覆盖刚刷的 1）
      i++; j++
    } else if (num === 1) {
      nums[j] = 1
      j++
    }
  }
  // 剩余位置刷 2
  for (let k = j; k < nums.length; k++) nums[k] = 2
}

题干：nums1 长度 m+n（后 n 个为 0），合并 nums2 进 nums1，保持有序。

var merge = function (nums1, m, nums2, n) {
  let i = m - 1
  let j = n - 1
  let k = m + n - 1 // 从后往前填

  while (i >= 0 && j >= 0) {
    if (nums1[i] > nums2[j]) {
      nums1[k] = nums1[i]
      i--
    } else {
      nums1[k] = nums2[j]
      j--
    }
    k--
  }
  // nums2 还有剩余就补上
  while (j >= 0) {
    nums1[k] = nums2[j]
    j--; k--
  }
}