二叉树的层序遍历、买卖股票的最佳时机、三数之和

二叉树的层序遍历

给定二叉树的根节点 root ，返回其节点值的层序遍历。即逐层地，从左到右访问所有节点。

示例：

输入：root = [3,9,20,null,null,15,7]

输出：[[3],[9,20],[15,7]]

思路：需要先用 n 标识 quene 长度，以确定这层有多少个元素；再用 level 保存该层所有元素的值，在循环结束时推入 res

tsCopy
function levelOrder(root: TreeNode | null): number[][] {
  if (!root) {
    return [];
  }

  let quene = [],
    res = [];
  quene.push(root);

  while (quene.length > 0) {
    const level = [];
    const n = quene.length;

    for (let i = 0; i < n; i++) {
      const node = quene.shift();
      const l = node.left,
        r = node.right;

      // 注意结果需要的是 val
      level.push(node.val);

      l && quene.push(l);
      r && quene.push(r);
    }

    res.push(level);
  }

  return res;
}

买卖股票的最佳时机

给定一个数组 prices ，它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。

你只能选择某一天买入这只股票，并选择在未来的某一个不同的日子卖出该股票。设计一个算法来计算你所能获取的最大利润。

返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回 0 。

示例 1：

输入：[7,1,5,3,6,4]

输出：5

解释：在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6 - 1 = 5 。 注意利润不能是 7 - 1 = 6, 因为卖出价格需要大于买入价格；同时，你不能在买入前卖出股票。

示例 2：

输入：[7,6,4,3,1]

输出：0

解释：在这种情况下, 没有交易完成, 所以最大利润为 0。

思路：状态转移方程。dp0 = max(卖出，dp0), dp1 = max(买入, dp1)。其中买入在这里直接是 0 - dp[i]

tsCopy
function maxProfit(prices: number[]): number {
  if (prices.length < 1) {
    return 0;
  }
  let dp0 = 0,
    dp1 = -Infinity; // 方便被后面的 -prices[i] 覆盖

  for (let i = 0; i < prices.length; i++) {
    dp0 = Math.max(dp1 + prices[i], dp0);
    // 只能交易一次，所以 -prices[i] 代表唯一的这一次买入
    dp1 = Math.max(-prices[i], dp1);
  }

  // 最后一天已卖出肯定比还没卖出强
  return dp0;
}

三数之和

给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 0 。请返回所有和为 0 且不重复的三元组。

注意：答案中不可以包含重复的三元组。

示例 1：

输入：nums = [-1,0,1,2,-1,-4]

输出：[[-1,-1,2],[-1,0,1]]

解释：

nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0

nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0

nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0

不同的三元组是 [-1,0,1] 和 [-1,-1,2]。

注意，输出的顺序和三元组的顺序并不重要。

思路：拆解成 nums[i] + (n-1)sum 问题。base case 为 n = 2 的情况，需要双指针从两边往里找具体的两个数字，满足和为 target 的条件。功能函数入参为 nums, n, start（不然会重复）, 目标和 target

tsCopy
function threeSum(nums: number[]): number[][] {
  nums.sort((a, b) => a - b);
  return solution(nums, 3, 0, 0);
}

const solution = (nums: number[], n: number, start: number, target: number) => {
  const size = nums.length;
  const res = [];

  // n < 2 和 nums 长度小于 n 都无效
  if (n < 2 || size < n) {
    return res;
  }

  // base case: n === 2，则正常从两边开始向里查找
  if (n === 2) {
    let low = start,
      high = size - 1;

    while (low < high) {
      const sum = nums[low] + nums[high];
      const left = nums[low],
        right = nums[high];

      if (sum < target) {
        while (low < high && nums[low] === left) low++;
      } else if (sum > target) {
        while (low < high && nums[high] === right) high--;
      } else {
        // 注意返回的是具体的数字 left 和 right，而不是下标 low 和 high
        res.push([left, right]);

        while (low < high && nums[low] === left) low++;
        while (low < high && nums[high] === right) high--;
      }
    }
    return res;
  }

  // 注意 i 需要从 start 开始
  for (let i = start; i < size; i++) {
    // 遍历每一个 i，并找出 nums[i] 要凑成 target 的 (n-1)sum
    const need = solution(nums, n - 1, i + 1, target - nums[i]);
    // 需要用拓展运算符，因为 need 本身就是二维数组，直接返回会变成三维数组
    res.push(...need.map((items) => [nums[i], ...items]));

    // 跳过相同的元素
    while (nums[i] === nums[i + 1] && i < size - 1) {
      i++;
    }
  }

  return res;
};