对撞指针

对撞指针的模板是什么？

• left 指向数组左端, right 指向右端;
• 每轮根据当前状态决定移动 left 还是 right;
• 终止条件为两指针相遇;

left, right = 0, len(nums) - 1
while left < right:
    if 满足目标:
        return 结果
    elif 需要更大:
        left += 1
    elif 需要更小:
        right -= 1
return 未找到

有序数组的两数之和如何求解？

• 和偏小说明 left 处元素不够大, left++;
• 和偏大说明 right 处元素过大, right--;
• 每轮排除一个元素, 时间 O(n), 空间 O(1);

function twoSum(numbers: number[], target: number): number[] {
  let left = 0;
  let right = numbers.length - 1;
  while (left < right) {
    const sum = numbers[left] + numbers[right];
    if (sum === target) return [left + 1, right + 1];
    else if (sum < target) left++;
    else right--;
  }
  return [-1, -1];
}

三数之和如何转化为两数之和？

• 先排序, 固定一个数 nums[i], 在 [i+1, n-1] 上用对撞指针找两数使其和为 -nums[i];
• 去重: 固定项与前一项相等时跳过; 命中后跳过左右两侧的重复值;
• 最接近的三数之和同理, 只是把命中条件换成维护 |target - sum| 的最小值;

function threeSum(nums: number[]): number[][] {
  nums.sort((a, b) => a - b);
  const res: number[][] = [];
  for (let i = 0; i < nums.length; i++) {
    if (i > 0 && nums[i - 1] === nums[i]) continue;
    let j = i + 1;
    let k = nums.length - 1;
    while (j < k) {
      const sum = nums[i] + nums[j] + nums[k];
      if (sum === 0) {
        res.push([nums[i], nums[j], nums[k]]);
        while (j < k && nums[j] === nums[j + 1]) j++;
        while (j < k && nums[k] === nums[k - 1]) k--;
        j++;
        k--;
      } else if (sum < 0) j++;
      else k--;
    }
  }
  return res;
}

• 时间复杂度: O(n^2); 空间复杂度: O(n) (排序与结果);

盛最多水的容器为什么移动较短的一边？

• 容量为 min(height[left], height[right]) * (right - left);
• 若移动较高的一边, 宽度变小而高度上限不变, 容量不可能增大;
• 只有移动较短的一边, 才可能因高度上限提高而得到更大容量;

function maxArea(height: number[]): number {
  let left = 0;
  let right = height.length - 1;
  let cap = 0;
  while (left < right) {
    cap = Math.max(cap, Math.min(height[left], height[right]) * (right - left));
    if (height[right] > height[left]) left++;
    else right--;
  }
  return cap;
}

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

有效三角形的个数如何用对撞指针统计？

• 排序后固定最长边 nums[i], 在 [0, i-1] 上用对撞指针;
• nums[left] + nums[right] > nums[i] 时, [left, right) 中任取一个下标与 right 组合都成立, 一次累加 right - left;
• 否则 left 太小, left++;
• 固定最长边的理由: 固定最小边时无法确定该移动 left 还是 right;

function triangleNumber(nums: number[]): number {
  nums.sort((a, b) => a - b);
  let res = 0;
  for (let i = 2; i < nums.length; i++) {
    let left = 0;
    let right = i - 1;
    while (left < right) {
      if (nums[left] + nums[right] > nums[i]) {
        res += right - left;
        right--;
      } else left++;
    }
  }
  return res;
}

• 时间复杂度: O(n^2); 空间复杂度: O(log n) (排序栈);