题解 | #买卖股票的最好时机 ii#

/**
 *
 * @param num int整型一维数组
 * @return int整型二维数组
 */
function threeSum(num) {
  // write code here
  if (num.length <= 2) return [];

  //   先排序
  num = num.sort((a, b) => a - b);

  //   通过Map 进行结果去重 初始化一个Map
  let resMap = new Map();
  //   遍历整个数组从第一个开始，既然求三数之和，那么第一个数字我们知道后
  // 后面两个数字相加等于第一个数字的反数

  for (let i = 0; i < num.length; i++) {
    let target = num[i];
    // [ -40, -10, -10, 0, 10, 20 ]
    // 创建指针进行范围缩小
    let left = i + 1;
    let right = num.length - 1;

    while (left < right) {
      if (target < -(num[left] + num[right])) {
        // 左边指针和右边指针相加 如果结果 大于 我们目标值的反数
        // target < -(num[left] + num[right]);
        // 我们需要将左指针向右移动
        // 因为目前二者的和取反 已经大于目标target
        // 只有将左指针向右移动 因为是递增的数组 左指针增大，
        //右指针已经是最大 二者之和取反他们的结果是逐渐减小

        left++;
      } else if (target > -(num[left] + num[right])) {
        // 当我们的目标值target 大于我们左右指针之和的反数是时，
        // 我们需要将右指针向左移动逐渐正大指针和的反数
        right--;
      } else {
        // 此时我们的目标值 跟我们的指针之和相等 说明我们找到了三元数
        let itemArr = [target, num[left], num[right]];

        // 我们通过数组作为key 是无法通过 Map的has方法判断当前属性是否存在的
        // 所以我们此处需要将我们的结果值 进行呢 JSON序列化
        // 转换成字符串格式进行比较是否存储
        itemArr = JSON.stringify(itemArr);
        if (!resMap.has(itemArr)) {
          resMap.set(itemArr, "1");
        }

        // 这种情况是为了保证我们第一次指针行动后，中间部分可能
        // 还存在其他结果的值
        if (num[left] === num[left + 1]) left++;

        if (num[right] === num[right - 1]) right--;

        // 如果当前while循环完毕了 我们将指针进行移动 进行下一位数字的比较
        left++;
        right--;
      }
    }
  }

  //   将数据转换成二维数组
  let resArr = Array.from(resMap.keys());
  return resArr.map((item) => JSON.parse(item));
}
module.exports = {
  threeSum: threeSum,
};