🧮

双指针法

题目描述 — 双指针

给你两个有序整数数组 nums1 和 nums2,请你将 nums2 合并到 nums1 中,使 nums1 成为一个有序数组。
注: 初始化 nums1 和 nums2 的元素数量分别为 m 和 n 。 你可以假设 nums1 有足够的空间(空间大小大于或等于 m + n)来保存 nums2 中的元素。
示例
输入:
nums1 = [1, 2, 3, 0, 0, 0], m = 3
nums2 = [2, 5, 6], n = 3
输出: [1, 2, 2, 3, 5, 6]

解题思路

  1. 记录 nums1, nums2 和 m + n 的有效长度
  1. 比较 i 和 j 指针所指向的值, 较大的移动到末尾 k
  1. 处理特殊情况
    1. i 指针剩余, 则不需要进行其他操作, 因为 nums1 本来就是需要返回值
    2. j 指针剩余, 需要将 nums2 继续添加到 nums1 中
/**
 * @param {number[]} nums1
 * @param {number} m
 * @param {number[]} nums2
 * @param {number} n
 * @return {void} Do not return anything, modify nums1 in-place instead.
 */
const mergeOrderedArray = (nums1, m, nums2, n) => {
    // 指向 nums1 有效尾部
    let i = m - 1
    // 指向 nums2 有效尾部
    let j = n - 1
    // 指向 nums1 + nums2 有效尾部
    let k = m + n - 1
    while (i >= 0 && j >= 0) {
        // 取较大值添加到 nums1[k] 处
        if (nums1[i] >= nums2[j]) {
            nums1[k] = nums1[i]
            // 移动指针位置
            i--
        } else {
            nums1[k] = nums2[j]
            // 移动指针位置
            j--
        }
        k--
    }
    // 如果 j 先遍历完, 则不需要额外处理, 因为 nums1 本来就是需要返回值
    // 如果 i 先遍历完, 需要将 nums2 继续添加到 nums1 中
    if (j >= 0) {
        nums1[k] = nums2[j]
        j--
        k--
    }
}

题目描述 — 指针碰撞

给你一个包含 n 个整数的数组 nums,判断 nums 中是否存在三个元素 a,b,c ,使得 a + b + c = 0 ?请你找出所有满足条件且不重复的三元组。
注: 答案中不可以包含重复的三元组。
示例
给定数组 nums = [-1, 0, 1, 2, -1, -4],
满足要求的三元组集合为: [ [-1, 0, 1], [-1, -1, 2] ]

解题思路