Leetcode - 数组的应用

1-两数求和问题

真题描述

给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。

你可以假设每种输入只会对应一个答案。但是，你不能重复利用这个数组中同样的元素。

示例: 给定 nums = [2, 7, 11, 15], target = 9
因为 nums[0] + nums[1] = 2 + 7 = 9 所以返回 [0, 1]

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */
const twoSum = function(nums, target) {

}

题目来源： leetcode-1-两数之和

思路分析

1. 暴力求解：两层循环
时间复杂度：O(N^2)
2. Map/Set
for循环 i:0->length O(N)
Map: 9-nums[i] 是否在数组中存在 O(1)
总的时间复杂度：O(N)

【分析】

• 当发现自己的代码里有两层循环时，先反思一下，能不能用空间换时间，把它优化成一层循环。
• 这道题空间换时间，Map 来帮忙--增加一个 Map 来记录已经遍历过的数字及其对应的索引值。
• 几乎所有的求和问题，都可以转化为求差问题。

题解

这里只给出时间复杂度为 O(N)的题解

用 ES6 中的 Map 来实现

const twoSum = function(nums, target) {
  const map = new Map();
  const len = nums.length;
  for (i = 0; i < len; i++) {
    let temp = target - nums[i];
    if (map.has(temp)) {
      return [map.get(temp), i];
    }
    map.set(nums[i], i);
  }
};

88-合并两个有序数组

真题描述

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

说明: 初始化 nums1 和 nums2 的元素数量分别为 m 和 n 。

你可以假设 nums1 有足够的空间（空间大小大于或等于 m + n）来保存 nums2 中的元素。

示例: 输入: (nums1 = [1, 2, 3, 0, 0, 0]), (m = 3);
(nums2 = [2, 5, 6]), (n = 3);
输出: [1, 2, 2, 3, 5, 6];
/**
 * @param {number[]} nums1
 * @param {number} m
 * @param {number[]} nums2
 * @param {number} n
 * @return {void} Do not return anything, modify nums1 in-place instead.
 */
var merge = function(nums1, m, nums2, n) {};

题目来源： leetcode-88

思路分析

Possible solutions

1. 合并后排序

最朴素的解法就是将两个数组合并之后再排序。

复杂度分析

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

1. 双指针 / 从前往后

一般而言，对于有序数组可以通过 双指针法 达到 O(n + m)的时间复杂度。

最直接的算法实现是将指针 p1 置为 nums1 的开头， p2 为 nums2 的开头，在每一步将最小值放入输出数组中。

由于 nums1 是用于输出的数组，需要将 nums1 中的前 m 个元素放在其他地方，也就需要 O(m) 的空间复杂度。

复杂度分析

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

1. 双指针 / 从后往前

方法二已经取得了最优的时间复杂度 O(n + m)，但需要使用额外空间。这是由于在从头改变 nums1 的值时，需要把 nums1 中的元素存放在其他位置。

如果我们从结尾开始改写 nums1 的值又会如何呢？这里没有信息，因此不需要额外空间。

这里的指针 p 用于追踪添加元素的位置。

由于 nums1 的有效部分和 nums2 并不一定是一样长的。我们还需要考虑其中一个提前到头的这种情况：

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

复杂度分析

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

题解

双指针 / 从后往前

var merge = function(nums1, m, nums2, n) {
  let i = m - 1,
    j = n - 1,
    k = m + n - 1;
  while (i >= 0 && j >= 0) {
    if (nums1[i] <= nums2[j]) {
      nums1[k--] = nums2[j--];
    } else {
      nums1[k--] = nums1[i--];
    }
  }
  while (j >= 0) {
    nums1[k--] = nums2[j--];
  }
};

15-三数求和问题

真题描述：三数之和

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

示例：
给定数组 nums = [-1, 0, 1, 2, -1, -4]，
满足要求的三元组集合为： [ [-1, 0, 1], [-1, -1, 2] ]
/**
 * @param {number[]} nums
 * @return {number[][]}
 */
var threeSum = function(nums) {

};

题目来源： leetcode-15

思路分析

思路

1. 暴力：三层循环 O(N^3)
2. 两层暴力+hash(Map/Set) O(N^2)
3. 先排序，再夹逼 时间复杂度取决于排序算法 --经典解法

审题

• 返回不重复的三元组
• 会有复数，无序？
• 可能不存在（实际要求返回空数组）
• a+b=-c
• 数组内有重复数字，结果有可能有重复

反馈：

• 通过一些边界条件，加速代码

问题：

• 如何在 hash 很好的避免结果集重复？

题解

先排序，再夹逼

/**
 * @param {number[]} nums
 * @return {number[][]}
 */
const threeSum = function(nums) {
  // 用于存放结果数组
  let res = [];
  // 目标值为0
  let sum = 0;
  // 给 nums 排序
  nums.sort((a, b) => 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;
};

[914]卡牌分组

真题描述

/**
 * @param {number[]} deck
 * @return {boolean}
 */
var hasGroupsSizeX = function(deck) {};

题目来源： leetcode-914-卡牌分组

思路分析

Possible solutions

1. 暴力？先统计每个数出现的次数，用对象 temp 保存，记其中最小的值为 min，然后从 2 到 min 枚举，看能否有数字可以将 temp 中的所有元素整除。
2. {}/Map + 最大公约数

解法

排序+最大公约数

/**
 * @param {number[]} deck
 * @return {boolean}
 */
const hasGroupsSizeX = function(deck) {
  if (deck.length === 1) {
    return false;
  } else {
    // 最大公约数
    const gcdFn = (a, b) => {
      // 利用辗转相除法来计算最大公约数
      let c = a % b;
      if (c === 0) return b;
      return gcdFn(b, c);
    };
    deck.sort((a, b) => a - b);
    let count = 1;
    let gcd;
    for (let i = 1; i < deck.length; i++) {
      if (deck[i] === deck[i - 1]) {
        count++;
      } else {
        if (count === 1) {
          return false;
        } else {
          if (gcd === undefined) {
            gcd = count;
          } else {
            gcd = gcdFn(gcd, count);
          }
          count = 1;
        }
      }
    }
    // 最后
    if (gcd === undefined) {
      gcd = count;
    } else {
      gcd = gcdFn(gcd, count);
    }
    if (gcd >= 2) {
      return true;
    } else {
      return false;
    }
  }
};

【283】移动零

真题描述

给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。

示例:

输入: [0,1,0,3,12]
输出: [1,3,12,0,0]
说明:

必须在原数组上操作，不能拷贝额外的数组。
尽量减少操作次数。

/**
 * @param {number[]} nums
 * @return {void} Do not return anything, modify nums in-place instead.
 */
var moveZeroes = function(nums) {

};

题目来源： leetcode-283-移动零

思路分析

Possible solutions

1. 定义一个指针 j，让它从数组左边开始移动；当遍历数组的时候，发现某个值不等于0，同时满足 i !== j 就让 nums[j] 与 nums[i] 交换位置，j++
// 1. 定义一个指针 j，让它从数组左边开始移动；当遍历数组的时候，发现某个值不等于0，就让 nums[j] = nums[i]，如果 i !== j, nums[i] = 0, j++

题解

/**
 * @param {number[]} nums
 * @return {void} Do not return anything, modify nums in-place instead.
 */
var moveZeroes = function(nums) {
  let j = 0;
  for (let i = 0; i < nums.length; i++) {
    if (nums[i] !== 0) {
      nums[j] = nums[i];
      if (i !== j) {
        nums[i] = 0;
      }
      j++;
    }
  }
};
// i !== j 这个判断条件，主要是考虑数组第一个元素可能非0?

稍稍改造一下：

/**
 * @param {number[]} nums
 * @return {void} Do not return anything, modify nums in-place instead.
 */
var moveZeroes = function(nums) {
  let j = 0;
  for (let i = 0; i < nums.length; i++) {
    if (nums[i] !== 0) {
      if (i !== j) {
        [nums[i], nums[j]] = [nums[j], nums[i]];
      }
      j++;
    }
  }
};

总结

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

数组本身这种数据结构不难，所以相关题目若想往难了出，那一定是要结合一些超越数据结构本身的东西——比如排序算法、二分思想、动态规划思想等等。因此，这部分对应的难题、综合题，我们需要等知识体系完全构建起来之后，在真题训练环节重新复盘。