算法通关村第五关——n数之和问题解析

1. 两数之和问题

力扣第1题就是两数之和问题，给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那两个整数，并返回它们的数组下标。你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。你可以按任意顺序返回答案。

第一种方法是用两层循环解决，第一层for循环确定一个数，第二层for循环确定第二个数，这种方法虽然简单但是时间复杂度为 $O(n^2)$,我们可以使用哈希表法来将寻找第二个数的时间复杂度降低，从 $O(n)$ 降到 $O(1)$.

  const prevNums = {};                    // 存储出现过的数字，和对应的索引               for (let i = 0; i < nums.length; i++) {       // 遍历元素   const curNum = nums[i];                     // 当前元素   const targetNum = target - curNum;          // 满足要求的目标元素   const targetNumIndex = prevNums[targetNum]; // 在prevNums中获取目标元素的索引if (targetNumIndex !== undefined) {         // 如果存在，直接返回 [目标元素的索引,当前索引]return [targetNumIndex, i];} else {                                    // 如果不存在，说明之前没出现过目标元素prevNums[curNum] = i;                     // 存入当前的元素和对应的索引}}

拓展:发散思维一下，如果返回的是两个值还可以用另外一种解法，双指针法：

// 双指针法
function twoSum(nums, target) {const hashTable = [];const lengthOfNums = nums.length;let first = 0;let second = lengthOfNums - 1;nums.sort((a, b) => a - b);// 特判if (lengthOfNums <= 1) return null;while (first < second) {if (nums[first] > target) return null;// first和second枚举的值要与上一个不同if (nums[first] + nums[second] === target) {hashTable.push([nums[first], nums[second]])while (nums[first] === nums[first + 1]) first++;while (nums[second] === nums[second - 1]) second--;first++;second--;}else if (nums[first] + nums[second] > target) second--;}return hashTable;
}

2.三数之和问题

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

分析：

首先，三层循环想都不要想！时间复杂度太高了，直接放弃。比较好的办法就是“排序+双指针”。先将数组升序排序，之后固定一位元素，再用两数之和思想找剩下的两个元素。

function threeSum(nums) {const lengthOfNums = nums.length;// 特判if (lengthOfNums < 3 || nums === null) {return [];}nums.sort((a, b) => a - b);let bucket = [];for (let first = 0; first < lengthOfNums; first++) {// 如果排序好的数组的第一个元素都大于0，那么就不会有三数之和等于0的情况if (nums[first] > 0) {break;}// 为了避免得到重复结果，需要和上一次枚举的数不相同if (first > 0 && nums[first] === nums[first - 1]) continue;let second = first + 1;let third = lengthOfNums - 1;while (second < third) {const sumOfThreeNums = nums[first] + nums[second] + nums[third];if (sumOfThreeNums === 0) {bucket.push[[nums[first], nums[second], nums[third]]];while (second < third && nums[second] === nums[second + 1]) second++; // 去重while (second < third && nums[third] === nums[third - 1]) third--; // 去重second++;third--;}else if (sumOfThreeNums < 0) second++;else third--;}}return bucket;
}