哈希表 - 三数之和

15. 三数之和

在这里插入图片描述

方法一：排序+双指针

/*** @param {number[]} nums* @return {number[][]}*/
var threeSum = function(nums) {const res = [], len = nums.length;// 将数组排序nums.sort((a, b) => a - b)for (let i = 0; i < len; i++) {let l = i + 1, r = len - 1, iNum = nums[i];// 将数组排过序，如果第一个数大于0直接返回resif (iNum > 0) return res// 去重if (iNum == nums[i - 1]) continuewhile (l < r) {let lNum = nums[l], rNum = nums[r], threeSum = iNum + lNum + rNum// 三数之和小于0，则左指针向右移动if (threeSum < 0) l++else if (threeSum > 0) r--else {res.push([iNum, lNum, rNum])// 去重while (l < r && nums[l] == nums[l + 1]) {l++}while (l < r && nums[r] == nums[r - 1]) {r--}l++r--}}}return res
};

方法二：递归

/***  nsum通用解法，支持2sum，3sum，4sum...等等*  时间复杂度分析：*  1. n = 2时，时间复杂度O(NlogN)，排序所消耗的时间。、*  2. n > 2时，时间复杂度为O(N^n-1)，即N的n-1次方，至少是2次方，此时可省略排序所消耗的时间。举例：3sum为O(n^2)，4sum为O(n^3)* @param {number[]} nums* @return {number[][]}*/
var threeSum = function (nums) {// nsum通用解法核心方法function nSumTarget(nums, n, start, target) {// 前提：nums要先排序好let res = [];if (n === 2) {res = twoSumTarget(nums, start, target);} else {for (let i = start; i < nums.length; i++) {// 递归求(n - 1)sumlet subRes = nSumTarget(nums,n - 1,i + 1,target - nums[i]);for (let j = 0; j < subRes.length; j++) {res.push([nums[i], ...subRes[j]]);}// 跳过相同元素while (nums[i] === nums[i + 1]) i++;}}return res;}function twoSumTarget(nums, start, target) {// 前提：nums要先排序好let res = [];let len = nums.length;let left = start;let right = len - 1;while (left < right) {let sum = nums[left] + nums[right];if (sum < target) {while (nums[left] === nums[left + 1]) left++;left++;} else if (sum > target) {while (nums[right] === nums[right - 1]) right--;right--;} else {// 相等res.push([nums[left], nums[right]]);// 跳过相同元素while (nums[left] === nums[left + 1]) left++;while (nums[right] === nums[right - 1]) right--;left++;right--;}}return res;}nums.sort((a, b) => a - b);// n = 3，此时求3sum之和return nSumTarget(nums, 3, 0, 0);
};