分离指针

分离指针的模板是什么？

• 两个指针各属于一个数组, 初始指向数组开头或末尾;
• 每轮根据两个当前元素的比较结果推进其中一个 (或同时推进);
• 任一数组遍历完即结束;

i = 0
j = 0
while i < len(nums1) and j < len(nums2):
    if 同时推进的条件:
        i += 1
        j += 1
    elif 只推进 i:
        i += 1
    else:
        j += 1

如何合并两个有序数组？

• 从尾部倒序合并, 避免覆盖 nums1 中尚未比较的元素;
• i、j 分别指向 nums1 有效段与 nums2 的末尾, k 指向 nums1 的末尾;
• 取较大者写入 nums1[k] 并让对应指针左移;
• 只剩 nums2 有剩余时继续写入; 只剩 nums1 有剩余时无需移动;

function mergeSorted(nums1: number[], m: number, nums2: number[], n: number): void {
  let i = m - 1;
  let j = n - 1;
  let k = m + n - 1;
  while (i >= 0 && j >= 0) {
    nums1[k--] = nums1[i] > nums2[j] ? nums1[i--] : nums2[j--];
  }
  while (j >= 0) nums1[k--] = nums2[j--];
}

• 时间复杂度: O(m + n); 空间复杂度: O(1);

如何求两个数组的交集？

• 两个数组都先排序;
• 元素相等则加入结果 (用 Set 去重) 并同时右移;
• 否则只右移元素较小的一侧;

function intersection(nums1: number[], nums2: number[]): number[] {
  nums1.sort((a, b) => a - b);
  nums2.sort((a, b) => a - b);
  let i = 0;
  let j = 0;
  const res = new Set<number>();
  while (i < nums1.length && j < nums2.length) {
    if (nums1[i] === nums2[j]) {
      res.add(nums1[i]);
      i++;
      j++;
    } else if (nums1[i] > nums2[j]) j++;
    else i++;
  }
  return [...res];
}

• 时间复杂度: O(n log n), 瓶颈在排序; 空间复杂度: O(n);

如何用字符串模拟大数相加？

• 指针从两串末尾出发, 逐位相加并把结果前插到结果数组;
• 用 carry 记录进位, 某串越界时该位按 0 参与运算;
• 循环条件包含 carry !== 0, 以保留最高位产生的进位;

function addStrings(num1: string, num2: string): string {
  let right1 = num1.length - 1;
  let right2 = num2.length - 1;
  const sum: string[] = [];
  let carry = 0;
  while (carry !== 0 || right1 >= 0 || right2 >= 0) {
    const value1 = right1 >= 0 ? Number(num1[right1]) : 0;
    const value2 = right2 >= 0 ? Number(num2[right2]) : 0;
    right1--;
    right2--;
    let value = value1 + value2 + carry;
    carry = value >= 10 ? 1 : 0;
    if (value >= 10) value %= 10;
    sum.unshift(String(value));
  }
  return sum.join("");
}

如何把大数相加扩展到任意进制？

• 把进位基数从 10 换成 B, 逐位加法逻辑完全一致;
• 需要一对"进制字符 ↔ 数值"的互转函数;
• 以 36 进制为例, 字符集为 0-9 与 a-z, 满 36 进一;

const offset = "a".charCodeAt(0) - 10;

const getInt = (ch: string): number => {
  if (ch >= "0" && ch <= "9") return Number(ch);
  return ch.charCodeAt(0) - offset;
};

const getChar = (num: number): string => {
  if (num >= 0 && num <= 9) return String(num);
  return String.fromCharCode(num + offset);
};

// 1b + 2x = 48 (36 进制)

• 时间复杂度: O(max(len(a), len(b))); 空间复杂度: O(max(len(a), len(b)));