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

Question

我在JavaScript会话中.在我的编码练习中找到这段代码.我理解逻辑,但我没有得到这个地图[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);

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

Answer 1

使用时间复杂度约为 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]}

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

希望能帮助到你..

Answer 2

该地图值你所看到的是一个查找表和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编写的，因此地图可以是对象而不是数组。这也将使调试容易得多；）

Answer 3

function twoSum(arr, S) {
 const sum = [];
  for(let i = 0; i< arr.length; i++) {
    for(let j = i+1;  j < arr.length; j++) {
      if(S == arr[i] + arr[j]) sum.push([arr[i],arr[j]])
    }
  }
 return sum
}

蛮力不是解决问题的最佳方法，但它确实有效。