使用 JavaScript 解答 LeetCode 第 1/15/18 题,两数之和、三数之和、四数之和。

N 数之和问题的解题思路是一脉相承的,从最基础的两数之和开始,逐步解决更复杂的计算。

两数之和

原题链接

本题是 LeetCode 题库第 1 题,由此访问。

题目描述

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

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

示例:

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

因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]

解题思路

两数之和问题有多种解题方法,暴力法是其中最简单的。暴力法的基本思路是,两次遍历数组,将两次遍历过程中取得的数字依次相加,如结果等于 target 值,返回两数对应下标。暴力法时间复杂度为 O(n^2),最差情况下需要两次完整的遍历才能取得结果。

我们需要对这一问题尽可能简化,使用哈希表对遍历结果进行存储,可以将两次遍历改为只需一次,时间复杂度控制在 O(n) 水平。根据题目描述,两数之和等于 target,那么在遍历过程中已经指定了其中一个数的下标(设为 n),另一个数则表示为 target-nums[n]。在哈希表中 target-n 键的值设为当前遍历值的下标,当遍历到后续的数字时,查询哈希表即可了解对应数的下标位置。将两个下标位置存储在数组内返回,即是最终答案。

AC 样例

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */
var twoSum = function(nums, target) {
    const hash = {};
    for(let x = 0; x < nums.length; x++) {
        if(hash[nums[x]] !== undefined) return [hash[nums[x]], x];
            else hash[target-nums[x]] = x;
    }
};

三数之和

原题链接

本题是 LeetCode 题库第 15 题,由此访问。

题目描述

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

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

示例:

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

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

解题思路

三数之和可以理解为是两数之和的复杂版本,暴力法的时间复杂度达到了 O(n^3)。参考题目描述,数字 abc 之间存在 a+b+c=0 的关系,可以简化为 b+c=-a。按照这一思路,可以将三重遍历简化为一次遍历+一次两数之和计算。

首先对数组进行升序排序。其次遍历数组,设为数字 a,在剩下的范围内求取 bc,判断其是否符合 b+c=-a 的关系。选取 bc 的过程中为提高效率,使用双指针,分别从数组内 a 之后的范围起止点开始,依次枚举两端数据进行比较。若两数之和大于 -a,则 c 端数字过大,向左移动后再判断;若两数之和小于 -a,则 b 端数字过小,向右移动后再判断;若两数之和等于 -a,则符合题目要求,以数组形式存储于最终结果数组。

当所有数字 a,及其 bc 遍历完成后,将最终结果二维数组返回。

升序排序使用快速排序算法,时间复杂度为 O(nlogn);求取 bc 过程中采用双指针方法,另根据题目要求避免重复数据产生,每次求取 bc 的最大搜索次数小于数组规模,这一过程时间复杂度为 O(n);对数字 a 采用一次遍历方法,时间复杂度为 O(n)。综上所述,本算法时间复杂度控制在 O(n^2)

AC 样例

/**
 * @param {number[]} nums
 * @return {number[][]}
 */
var threeSum = function(nums) {
    const res = [];
    // 数组排序
    nums = nums.sort((a, b) => a - b);
    // 遍历 a
    for(let x = 0; x < nums.length; x++) {
        // 重复 a 的排除
        if (x > 0 && nums[x] == nums[x-1]) continue;
        // 设 c 在 nums 最尾端
        let z = nums.length - 1;
        const target = -nums[x];
        for(let y = x + 1; y < nums.length; y++) {
            // 重复 b 的排除
            if(y > x + 1 && nums[y] == nums[y-1]) continue;
            // 保持 c 始终大于 b
            while(z > y && nums[z] + nums[y] > target) z--;
            // c b 一致时中止            
            if (z == y) break;
            if(nums[y] + nums[z] == target) res.push([nums[x], nums[y], nums[z]]);
        }
    }
    return res;
};

四数之和

原题链接

本题是 LeetCode 题库第 18 题,由此访问。

题目描述

给定一个包含 n 个整数的数组 nums 和一个目标值 target,判断 nums 中是否存在四个元素 a,b,c,d,使得 a + b + c + d 的值与 target 相等?找出所有满足条件且不重复的四元组。

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

示例:

给定数组 nums = [1, 0, -1, 0, -2, 2],和 target = 0。

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

解题思路

四数之和问题和三数之和类似,在暴力法情况下时间复杂度可达 O(n^4),这里我们将其简化,可得数字关系为 (c+d)=target-(a+b),即将四个数的匹配过程改为两次遍历+一次两数之和计算,整体时间复杂度可控制在 O(n^3) 水平。

首先对数组进行升序排序,之后遍历 ab,在遍历过程中需要注意去重。在一次循环中,数字 ab 确定的情况下,求取符合条件的数字 cd。基本思路与三数之和一致。

对数组排序使用快速排序算法,时间复杂度 O(nlogn);针对数字 ab 的遍历,是两次循环,时间复杂度为 O(n^2);求取数字 cd 过程中使用双指针,并且为满足不产生重复数据的要求,每次搜索次数小于数组规模,故时间复杂度为 O(n)。综上所述,本算法时间复杂度为 O(n^3)

AC 样例

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[][]}
 */
var fourSum = function(nums, target) {
    const res = [];
    nums = nums.sort((a, b) => a - b);
    for(let a = 0; a < nums.length; a++) {
        // 去重 a
        if(a > 0 && nums[a] == nums[a-1]) continue;
        for(let b = a + 1; b < nums.length; b++) {
            // 去重 b            
            if(b > a + 1 && nums[b] == nums[b-1]) continue;
            let d = nums.length - 1;
            for(let c = b + 1; c < nums.length; c++) {
                // 去重 c        
                if(c > b + 1 && nums[c] == nums[c-1]) continue;
                while(d > c && nums[a] + nums[b] + nums[c] + nums[d] > target) d--;
                if(d == c) break;
                if(nums[a] + nums[b] + nums[c] + nums[d] == target) res.push([nums[a], nums[b], nums[c], nums[d]]); 
            }
        }
    }

    return res;
};