来自指定数组的元素对，其总和等于特定目标数

Question

我正在我的 JavaScript 会话中。在我的编码练习中找到这段代码。我理解逻辑，但我没有得到这个 map[nums[x]] 条件。

 function twoSum(nums, target_num) {
    var map = [];
    var indexnum = [];

    for (var x = 0; x < nums.length; x++)
    {
        if (map[nums[x]] != null)
        // what they meant by map[nums[x]]
        {
            index = map[nums[x]];
            indexnum[0] = index+1;
            indexnum[1] = x+1;
            break;
        }
        else
        {
            map[target_num - nums[x]] = x;
        }
    }
    return indexnum;
    }
console.log(twoSum([10,20,10,40,50,60,70],50));

我正在尝试从指定数组中获取元素对，其总和等于特定目标数。我写了下面的代码。

 function arraypair(array,sum){
        for (i = 0;i < array.length;i++) {
            var first = array[i];
            for (j = i + 1;j < array.length;j++) {
                var second = array[j];

                if ((first + second) == sum) {
            alert('First: ' + first + ' Second ' + second + ' SUM ' + sum);
            console.log('First: ' + first + ' Second ' + second);
                }
            }

        }
}

var a = [2, 4, 3, 5, 6, -2, 4, 7, 8, 9];

arraypair(a,7);

有没有比上述两种解决方案更优化的方法？有人可以解释第一个解决方案 map[nums[x]] 这个条件究竟指向什么吗？

原文由 ShaMoh 发布，翻译遵循 CC BY-SA 4.0 许可协议

Answer 1

您看到的 地图 值是一个查找表，并且 twoSum 方法实现了所谓的 动态规划

在 动态规划 中，您存储计算的值，以后可以重新使用这些值来找到解决方案。

让我们研究一下它是如何工作的，以便更好地理解它：

 twoSum([10,20,40,50,60,70], 50)
//I removed one of the duplicate 10s to make the example simpler

在第 0 次迭代中：

值为 10。我们的目标数字是 50。 当我在索引 0 中看到数字 10 时，我记下如果我在此列表中找到 40 (50 - 10 = 40)，那么我可以在索引中找到它的对0。

所以在我们的地图中，40 点到 0。

在迭代 2 中：

价值是 40。我看地图我的地图看到我以前找到了一对 40。

map[nums[x]] （与 map[40] 相同）将返回0。

这意味着我在索引 0 处有一对 40。

0 和 2 组成一对。

---

这现在有意义吗？

与您有 2 个嵌套循环的解决方案不同，您可以存储以前计算的值。这将节省您的处理时间，但会浪费更多内存空间（因为查找表需要内存）

此外，由于您是用 javascript 编写的，因此您的 地图 可以是对象而不是数组。它还将使调试变得容易得多；）

原文由 user1589069 发布，翻译遵循 CC BY-SA 3.0 许可协议

Answer 2

使用时间复杂度约为 O(n) 的 HashMap 方法，下面是以下代码：

 let twoSum = (array, sum) => {
    let hashMap = {},
      results = []

        for (let i = 0; i < array.length; i++){
            if (hashMap[array[i]]){
                results.push([hashMap[array[i]], array[i]])
            }else{
                hashMap[sum - array[i]] = array[i];
            }
          }
          return results;
    }
console.log(twoSum([10,20,10,40,50,60,70,30],50));

结果：

 {[10, 40],[20, 30]}

我认为代码是不言自明的，即使你想要帮助理解它，也请告诉我。我很乐意为它做解释。

希望能帮助到你..

原文由 Pratswinz 发布，翻译遵循 CC BY-SA 3.0 许可协议