时间戳

首页 > 解决方案 > 如何改进：两个总和给定一个整数数组，返回两个数字的索引......使用角度

angular - 如何改进：两个总和给定一个整数数组，返回两个数字的索引......使用角度

问题描述

我一直在为下面提到的 leetcode 问题寻找更好的解决方案。

给定一个整数数组，返回两个数字的索引，使它们相加到一个特定的目标。

您可能会假设每个输入都只有一个解决方案，并且您可能不会两次使用相同的元素。

let 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]
            }
        }
    }
};

标签： angulartypescript

解决方案

我们可以使用 Map 在 O(n) 时间内完成此操作。遍历数组中的每个数字（比如说 num）并检查target - num地图中是否已经存在。如果它存在，则意味着在之前的迭代中我们已经看到了一个数字，当它添加到当前 num 时会返回目标。在每次迭代中，我们将当前的 num 作为键，并将它的索引作为 Map 中的值。

const twoSum = (nums, target) => {
    const map = new Map();

    for (let i = 0; i < nums.length; i++) {
        const diff = target - nums[i];
        if (map.has(diff)) {
            return [map.get(diff), i];
        }
        map.set(nums[i], i);
    }

    return [];
};
console.log(twoSum([1, 2, 3, 4, 5], 9));

推荐阅读