# 前言

最近准备好好开始刷 leetcode 了，而刷题之余写一些总结性质的东西我也觉得是非常有必要的。

最近刚好在回顾题目的时候看到了二数之和、三数之和、四数之和等等的题目，并且它们的解决方式都十分的类似，因此想着趁这个机会进行一些总结。

当然之后也会总结一些其他性质的题目，这次写文当作是一个开端吧，我希望我的算法水平能在日积月累中取得一些成效～～

# 二数之和

这道题目在 leetcode 上是排名 No.1，可见是无数入门算法的同学们的初见，对其感情之深（T v T）当然刚刚开始我也一头雾水没啥思路。

我觉得对于算法题而言，最重要的就是看到这个题目之后你要有思路怎么去解决。无论是数据结构、还是采用什么算法，都需要脑海里面蹦出来有一个解决这个问题的想法然后再付诸行动。 当然这个思路也是刷题刷出来的。

# 题目

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

你可以假设每种输入只会对应一个答案。但是，数组中同一个元素不能使用两遍。

示例:

给定 nums = [2, 7, 11, 15], target = 9

因为 nums [0] + nums [1] = 2 + 7 = 9

所以返回 [0, 1]。

# 解答

我们首先看这个题目，其实很简单，就是从一个数组中找到一个组合，让这个组合中的值和为 target。

那么很简单啊，直接来个循环遍历不就可以了？外一层里一层 for 循环不断相加，判断和是否为 target 即可。

当然这样是没问题！你可以很顺畅的写出来，但是这样子放在 leetcode 上面是通不过的，因为这个两数的时间复杂度就达到 $n^2$ 了，leetcode 上面的测试用例后面还涉及到巨量的数据，这怎么跑得通呢？

况且后面还有三、四、五数之和，两数的就得 $n^2$ ，三数的岂不是得 $n^3$ ？

先讲个结论：遇到这种你的第一直觉是循环遍历解决的问题，核心思路应该是怎么降低遍历次数。

对于这种 n 数之和的问题而言，是可以将原本的循环次数给降低一个维度的。

我们先来看看正常的 1 维循环写法（2 维的太过于无脑，在这里不写了）：

function twoSum1(nums: number[], target: number): number[] {

  // 1 维循环算法

  // 1. 将 nums 从小到大排列

  nums.sort((a, b) => a - b);

  // 2. 定义变量

  const length: number = nums.length;

  let end: number = length - 1;

  const resArr: number[] = [];

  // 3. 遍历数组

  for (let i = 0; i < length; i++) {

    if (i > 0 && nums[i] === nums[i - 1]) {

      continue;

    }

    while (nums[i] + nums[end] > target) {

      end--;

    }

    if (nums[i] + nums[end] === target) {

      resArr.push(i, end);

      break;

    }

  }

  return resArr;

}

首先调用数组的 sort 方法，将 nums 数组从小到大排序。

然后定义了三个变量： length 用于存储 nums 数组的长度； end 初始化为 nums 数组的最后一个元素的索引； resArr 是一个空数组，用于存储结果。

接下来，函数使用一个 for 循环遍历 nums 数组。在每次循环中，首先检查当前元素是否与前一个元素相同，如果相同，则跳过当前循环，进入下一次循环。因为在排序后的数组中，相同的元素会被放在一起，如果当前元素与前一个元素相同，那么它们的和肯定已经被计算过了。

然后使用一个 while 循环，不断地将 end 减 1，直到 nums[i] + nums[end] 的值不大于 target 。这是因为 nums 数组已经被排序，所以如果 nums[i] + nums[end] 的值大于 target ，那么只能通过减小 end 来减小它们的和。

最后，如果 nums[i] + nums[end] 的值等于 target ，那么就将 i 和 end 添加到 resArr 数组中，并跳出 for 循环。

函数最后返回 resArr 数组，即包含两个和为 target 的元素的索引的数组。

这个就是 n 数之和的模板套路写法！ 梳理一下整个解题的步骤：

1. 首先对传进来的数组进行从小到大的排序，便于之后的遍历。因为已知整个数组是从小到大的，我们可以从小开始遍历，然后取最大的开始进行相加，最后逐层的进行拟合。
2. 然后定义变量，主要的变量有：
   1. 数组长度 length
   2. 指针。这个指针按照是 n 数循环的问题，定义 n-1 个即可。
   3. 存储结果的数组 resArr。
3. 对整个 nums 数组进行最外层循环，遇到 nums [i] 和 nums [i-1] 相等的，直接跳过即可。
4. 在每一次的循环内部，遵循一个规律：只根据拟合结果同时改变最后两个指针的值，前面的 n-3 个指针全部都是根据 for 循环自身来改变。也就是说，这样子可以把原本的全部 for 循环给降低一层维度。

是不是还是有点云里雾里的？可以看一下三数之和的写法。

在这里我再附加一个对于特定的二数之和问题的哈希表写法 —— 借助 Map 的 get、set 方法来实现对于 target - nums [i] 的查找。

这个 Map 的 key 是这个 nums 数组中的数据值，value 是这个数据对应的 nums 数组的下标。这样子只要 get 对应的 value，就可以直接拿到其对应的下标了。

所以我们只用一次遍历，然后直接使用 get 看看能不能拿得到 target-nums [i] 的下标，能拿到就代表找到了。在这里也给出对应的算法代码：

	function twoSum(nums: number[], target: number): number[] {
	// 1. 生成一个 ma p，key 为 nums 的值，value 为 nums 的下标
	let helperMap: Map<number, number> = new Map();
	// 2. 定义一个变量，用来存储 map 中是否存在 target - nums [i] 的值
	let index: number | undefined;
	// 3. 定义结果数组
	let resArr: number[] = [];
	for (let i = 0; i < nums.length; i++) {
	index = helperMap.get(target - nums[i]);
	if (index !== undefined) {
	resArr = [i, index];
	}
	helperMap.set(nums[i], i);
	}
	return resArr;
	}

# 三数之和

# 题目

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

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

示例：

给定数组 nums = [-1, 0, 1, 2, -1, -4]，

满足要求的三元组集合为： [[-1, 0, 1], [-1, -1, 2] ]

# 解答

可以看到，三数之和要求我们返回的是全部的符合条件的三元组集合，返回形式是矩阵的形式。因此我们就必须得进行遍历，不然是根本找不出所有的组合。

我们可以按照上述方法如法炮制：

function threeSum(nums: number[]): number[][] {

  // 1. 对原数组进行排序 (从小到大)，便于之后遍历

  nums.sort((a, b) => a - b);

  // 2. 定义变量：数组长度，左指针，右指针，结果数组

  let length = nums.length;

  let left: number = 0; // 最左端

  let right: number = length - 1; // 最右端

  let resArr: number[][] = []; // 存放结果的数组

  // 3. 遍历数组

  for (let i = 0; i < length; i++) {

    // 特殊情况（两种）：

    // 3.1 nums 经过排序后，只要 nums [i]>0, 此后的 nums [i] + nums [left] + nums [right] 均大于 0, 可以提前终止循环。

    if (nums[i] > 0) {

      return resArr;

    }

    // 3.2 如果当前值与前一个值相同，则跳过

    if (i > 0 && nums[i] === nums[i - 1]) {

      continue;

    }

    // 3.3 更改左指针和右指针的值，缩小范围

    left = i + 1;

    right = length - 1;

    while (left < right) {

      // 3.4 如果三数之和等于 0，则将结果添加到结果数组中

      let total: number = nums[i] + nums[left] + nums[right];

      if (total === 0) {

        resArr.push([nums[i], nums[left], nums[right]]);

        left++;

        right--;

        // 如果左 / 右指针的值与前 / 后一个值相同，则跳过

        while (nums[right] === nums[right + 1]) {

          right--;

        }

        while (nums[left] === nums[left - 1]) {

          left++;

        }

      } else if (total < 0) {

        left++;

      } else {

        right--;

      }

    }

  }

  return resArr;

}

可以看到，是非常公式化的模板，唯一需要注意的就是 3.3 步开始的 while 循环判断。需要对 left < right 进行判断，因为 left 和 right 都是同时的进行右移 / 左移的。直到它们俩相遇，这一层的遍历才算是结束，开启下一个循环的遍历。

# 四数之和、五数之和、...

按照上述方法，我们其实也就很简单的可以写出四、五、n 数之和的公式化写法。在这里给出四数之和的写法：

function fourSum(nums: number[], target: number): number[][] {

  // 1. 对原数组进行排序

  nums.sort((a, b) => a - b);

  // 2. 定义变量：数组长度，第一个指针，第二个指针，第三个指针，第四个指针，结果数组

  let first: number = 0,

    second: number,

    third: number,

    fourth: number;

  let length: number = nums.length;

  let resArr: number[][] = [];

  // 3. 遍历数组

  for (; first < length; first++) {

    // 3.1 如果当前值与前一个值相同，则跳过

    if (first > 0 && nums[first] === nums[first - 1]) {

      continue;

    }

    // 3.2 更改第二个指针的值，缩小范围，并基于第二个指针遍历数组

    for (second = first + 1; second < length; second++) {

      // 也是跳过重复的值

      if (second - first > 1 && nums[second] === nums[second - 1]) {

        continue;

      }

      third = second + 1;

      fourth = length - 1;

      while (third < fourth) {

        let total: number =

          nums[first] + nums[second] + nums[third] + nums[fourth];

        if (total === target) {

          resArr.push([nums[first], nums[second], nums[third], nums[fourth]]);

          third++;

          fourth--;

          while (nums[third] === nums[third - 1]) third++;

          while (nums[fourth] === nums[fourth + 1]) fourth--;

        } else if (total < target) {

          third++;

        } else {

          fourth--;

        }

      }

    }

  }

  return resArr;

}

可见基本的模板都是相同的。

# 总结

n 数之和的套路十分单纯： 减少循环的嵌套层数 。虽然对于最后的 n 数问题，最理想的全遍历减少嵌套次数只能是一层，不过也是目前效率最高的一种解法。

由于我本人几乎没什么机会接触一些真正的算法相关知识，所以我只能在这个小博客进行一些比较粗浅的经验记录～如果有不合理的地方，希望浏览到这个文章的大家能够多多留言哈哈！

之后打算理一理链表相关的问题。