# 数组的应用

# 求和问题

真题描述：给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那两个整数，并返回他们的数组下标。 nums = [2, 7, 11, 15], target = 9 返回 [0,1]

# 解题思路

有两层循环时，先反思一下，能不能用空间换时间，把它优化成一层循环。
几乎所有的求和问题，都可以转化为求差问题。

# 解法一

const getTwoSum = (nums, target) => {
  // 缓存已遍历项 key记录值 值记录下标
  const diffs = {};
  for (let i = 0; i < nums.length; i++) {
    // 有可能为零 所以检查其是否为undefined
    if (diffs[target - nums[i]] !== undefined) {
      return [diffs[target - nums[i]], i];
    }
    diffs[nums[i]] = i;
  }
};

# 解法二

const getTwoSum2 = (nums, target) => {
  // 缓存已遍历项 key记录值 值记录下标
  const diffMap = new Map();
  for (let i = 0; i < nums.length; i++) {
    if (diffMap.has(target - nums[i])) {
      return [diffMap.get(target - nums[i]), i];
    }
    diffMap.set(nums[i], i);
  }
};

# 双指针

# 应用范围

双指针法用在涉及求和、比大小类的数组题目

# 前提

该数组必须有序

否则双指针根本无法帮助我们缩小定位的范围，压根没有意义。

# 真题应用

给你两个有序整数数组 nums1 和 nums2，请你将 nums2 合并到 nums1 中，使 nums1 成为一个有序数组。

输入: nums1 = [1,2,3,0,0,0], m = 3 nums2 = [2,5,6], n = 3 输出: [1,2,2,3,5,6]

每次只对指针所指的元素进行比较。 取其中较大的元素，把它从 nums1 的末尾往前面填补：

// - 代表指针所在
    -
1,2,3,0,0,0
    -
2,5,6

    -
1,2,3,0,0,6
    -
  2,5

    -
1,2,3,0,5,6
    -
    2

    -
1,2,3,0,5,6
    -
    2

  -
1,2,0,3,5,6
  -
  2

1,2,2,3,5,6

# for 循环实现

const merge = function (nums1, m, nums2, n) {
  const tlen = nums1.length;
  // nums1最后一位
  let max1 = m - 1;
  // nums2最后一位
  let max2 = n - 1;

  // 循环nums1
  for (let i = 0; i < tlen; i++) {
    // 目前需要填充的坑位
    const needFillIndex = tlen - i - 1;
    const isGet1 = nums1[max1] > nums2[max2];
    if (!nums2.length) {
      return nums1;
    }

    if (isGet1) {
      // 取nums1中有效位最大的值
      nums1[needFillIndex] = nums1[max1];
      max1--;
    } else {
      // 取nums2中有效位最大的值
      nums1[needFillIndex] = nums2.pop();
      max2--;
    }
  }
};

# while 实现

const merge2 = function (nums1, m, nums2, n) {
  let k = m + n - 1;
  // nums1最后一位
  let i = m - 1;
  // nums2最后一位
  let j = n - 1;

  while (i >= 0 && j >= 0) {
    if (nums1[i] > nums2[j]) {
      nums1[k] = nums1[i];
      i--;
      k--;
    } else {
      nums1[k] = nums2[j];
      j--;
      k--;
    }
  }

  while (j >= 0) {
    nums1[k] = nums2[j];
    j--;
    k--;
  }
  return nums1;
};

# 为什么是从后往前填补？

因为是要把所有的值合并到 nums1 里，所以说我们这里可以把 nums1 看做是一个容器。但是这个容器，它不是空的，而是前面几个坑有内容的。如果我们从前往后填补，就没法直接往对应的坑位赋值了（会产生值覆盖）。

从后往前填补，我们填的都是没有内容的坑，这样会省掉很多麻烦。

# 有效部分不一样

如果提前遍历完的是 nums1 的有效部分，剩下的是 nums2。那么这时意味着 nums1 的头部空出来了，直接把 nums2 整个补到 nums1 前面去即可。
如果提前遍历完的是 nums2，剩下的是 nums1。由于容器本身就是 nums1，所以此时不必做任何额外的操作。

# 对撞指针

左右指针一起从两边往中间位置相互迫近，这样的特殊双指针形态，被称为“对撞指针”。

# 什么时候你需要联想到对撞指针？

两个关键字——“有序”和“数组”。普通双指针走不通，立刻想对撞指针！

# 真题应用

给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有满足条件且不重复的三元组。

# 解题思路

把数组变得有序
对数组进行遍历一个数固定指针放右边一个放最前一个放最后
相加之和大于0，说明右侧的数偏大了，右指针左移
相加之和小于0，说明左侧的数偏小了，左指针右移
重复元素的跳过处理

/**
 * @param {number[]} nums
 * @return {number[][]}
 */
const threeSum2 = function (nums) {
  // 用于存放结果数组
  let res = [];
  // 给 nums 排序
  nums = nums.sort((a, b) => {
    return a - b;
  });
  // 缓存数组长度
  const len = nums.length;
  // 注意我们遍历到倒数第三个数就足够了，因为左右指针会遍历后面两个数
  for (let i = 0; i < len - 2; i++) {
    // 左指针 j
    let j = i + 1;
    // 右指针k
    let k = len - 1;
    // 如果遇到重复的数字，则跳过
    if (i > 0 && nums[i] === nums[i - 1]) continue;

    while (j < k) {
      // 三数之和小于0，左指针前进
      if (nums[i] + nums[j] + nums[k] < 0) {
        j++;
        // 处理左指针元素重复的情况
        while (j < k && nums[j] === nums[j - 1]) j++;
      } else if (nums[i] + nums[j] + nums[k] > 0) {
        // 三数之和大于0，右指针后退
        k--;

        // 处理右指针元素重复的情况
        while (j < k && nums[k] === nums[k + 1]) k--;
      } else {
        // 得到目标数字组合，推入结果数组
        res.push([nums[i], nums[j], nums[k]]);

        // 左右指针一起前进
        j++;
        k--;

        // 若左指针元素重复，跳过
        while (j < k && nums[j] === nums[j - 1]) j++;

        // 若右指针元素重复，跳过
        while (j < k && nums[k] === nums[k + 1]) k--;
      }
    }
  }

  // 返回结果数组
  return res;
};

← 数据结构字符串应用 →