在一个由若干整形数组成的数组中找到两个数的和等于给定的目标整数

给出一个由若干整数组成的数组和一个目标整数,返回两个数组的下标使得它们的值加起来正好等于这个目标整数。
你可以假设这个数组中的每个值都是唯一的,且只存在一对这样的下标(它们对应的值的和等于这个目标值)。
返回的下标组成的数组顺序随意。

案例一:
输入:nums = [2, 7, 11, 15], target = 9
输出:[0, 1]
解释:因为 nums[0] + nums[1] = 9, 所以最终得到的两个下标值 [0, 1]

案例二:
输入:nums = [3, 2, 4], target = 6
输出:[1, 2]

案例三:
输入:nums = [3, 3], target = 6
输出:[0, 1]

限制条件:

  • 2 <= nums.length <= 104
  • -109 <= nums[i] <= 109
  • -109 <= target <= 109
  • 仅存在唯一有效的答案

1. 时间复杂度为 O(n^2) 的计算方式

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */
var twoSum = function(nums, target) {
    for(let i = 0; i < nums.length; i++) {
        for(let j = i + 1; j < nums.length; j++) {
            if(nums[i] + nums[j] === target) {
                return [i, j];
            }
        }
    }
};

2. 利用Hashmap 时间复杂度为 O(n) 计算方案

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */

// O(n) hashmap solution
var twoSum = function(nums, target) {
    let map = new Map();
    for(let i = 0; i < nums.length; i++) {
        if(map.has(target - nums[i])) {
            // map.get will get the 1st number index and current number index
            return [map.get(target - nums[i]), i];
        }
        // set the number and its index
        map.set(nums[i], i)
    }
    return [];
}

评论

还没有评论...留下你的评论!

发表评论

电子邮件地址不会被公开。 必填项已用*标注

Sidebar