logo标签列表

Javascript两数之和算法：给定一个整数数组，返回两个数字的索引，使它们相加等于特定的目标值。

javascriptarraysalgorithm
5
给定一个整数数组，返回两个数字的索引，使它们加起来等于特定目标。
示例：给定nums = [3,2,4]，target = 6，因为nums[1] + nums[2] = 2 + 4 = 6，返回[1,2]。
解决方案：
var twoSum = function(nums, target) {
    for(let i = 0; i <= nums.length; i++){
        for(let j = 0; j <= nums.length; j++){
            if(nums[i] + nums[j] == target){
                return [i, j]
            }
        }
    }
};

上述代码在其他情况下都有效，但不适用于这种情况。

期望结果：[1,2]

输出结果：[0,0]

例如，我尝试使用不同的数字数组和不同的目标，即使更改数字的顺序也能正常运行。

示例：

新数组：[15, 7, 11, 2]，目标值为9，

输出结果：[1, 3]。

我不明白解决方案出了什么问题，希望有人能够解释。谢谢。

你所做的问题在于j是从0开始索引的。因此，它将考虑i处的任何元素两次。j应该始终为i+1。就你给出的例子而言，假设i=0且j=0，现在它将检查num[0]+num[0]，即3+3，并返回0,0。但问题说明不能重复使用任何数字。因此，如果您将j设置为i+1，则以这种方式3+2！=6将导致下一个元素。 - Simran Dhingra
22个回答
12

您可以使用一种非常简单的技术。
基本上，您可以检查目标值与当前迭代元素之间的差异是否存在于数组中。

假设同一索引不能两次使用

nums = [3, 2, 4], target = 6
nums[0] = 3
target = 6
diff = 6 - 3 = 3
nums.indexOf[3] = 0 // FAILURE case because it's the same index

// move to next iteration
nums[1] = 2
target = 6
diff = 6 - 2 = 4
nums.indexOf(4) = 2 // SUCCESS '4' exists in the array nums
// break the loop

这是由LeetCode接受的答案。

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */
var twoSum = function(nums, target) {
    for (let index = 0; index < nums.length; index++) {
        const diff = target - nums[index];
        const diffIndex = nums.indexOf(diff);
        // "diffIndex !== index" takes care of same index not being reused
        if (diffIndex !== -1 && diffIndex !== index) {
            return [index, diffIndex];
        }
    }
};

运行时间：72 毫秒，超过 93.74% 的 JavaScript 在线提交记录
内存使用：38.5 MB，少于 90.55% 的 JavaScript 在线提交记录。

还有谁能帮我减少内存使用呢？

这并没有回答“所提供的解决方案出了什么问题？” - greybeard
8
我不明白解决方案有什么问题，希望有人能解释一下？在这里，您的内部和外部循环都从第0个开始，所以在情况[3,2,4]和目标6时，它将返回[0,0]，因为3 + 3等于目标值，因此为了确保不重复使用相同索引的元素，在外部和内部循环之间创建一个差异为1的数组。
让外部循环从第0个索引开始，内部循环的值为i + 1。 

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

console.log(twoSum([15, 7, 11, 2],9))
console.log(twoSum([3, 2, 4],6))

当你找不到这两个数字时，你会返回什么？ - David G
@CodeManiac 啊，那么它将返回 undefined。我以为你必须返回一个空数组。 - David G
1
@0x499602D2 只是想避免猜测，因为问题中没有关于此的信息，所以将其保留为原始代码，但如果我必须这样做，我将始终保持相同类型的返回值，这样就可以直接从函数中使用返回值而不是检查返回值类型然后使用进一步操作。 - Code Maniac
3

这里有一种简单的方法，使用JavaScript并使用不同类型的输入来解决此问题并使其更有效。
例如，使用([3,3], 6)作为输入，期望输出将是[0,1]，而使用([3,2,4], 6)作为输入，期望输出将是[2,4]

var twoSum = function (nums, target) {
   for (let i = 0; i <= nums.length; i++) {
     for (let j = 0; j <= nums.length; j++) {
       if (i !== j) {
         if (nums[i] + nums[j] === target) {
           return [i, j];
         }
       }
     }
   }
 };
 console.log(twoSum([3, 2, 4], 6));
1
这并没有回答“所提供的解决方案有什么问题？” - greybeard
我认为这应该是正确的答案。因为它不会两次使用相同的元素。 - Dulya Perera
2
我们可以通过使用map / object在O（n）时间内解决此问题。 我们可以维护一个映射或对象，其中将保存所有值及其索引，然后我们可以迭代数组并为每个值查找target-nums [i]，并在map / object中找到该值。 让我们通过示例来看看：
nums=[2,7,11,15]
target = 9;
then map/object will be 
mm={
2 : 0,
7: 1,
11: 2,
15: 3
}


then for each value, we will find diff and find that diff in map/object.
for i=0 diff= 9-2=7 and mm.has(7) is true so our answer is 2 and 7. 
for their index we can use mm.get(7) and i. 
return [mm.get(7), i]


var twoSum = function(nums, target) {
    let mm=new Map();
    for(let i=0;i<nums.length;i++){
        mm.set(nums[i],i);
    }
    let diff=0;
    let j;
    for(let i=0;i<nums.length;i++){
        diff=target-nums[i];
        if(mm.has(diff) && i!=mm.get(diff)){
           j=mm.get(diff);
            if(j>i){
                return [i,j];
            }else{
               return [j,i];
            }
        }
    }
};

运行时间：76毫秒，快于88.18%的JavaScript在线提交的Two Sum问题。内存使用率：41.4 MB，少于13.32%的JavaScript在线提交的Two Sum问题。

它会对[2,15,11,2]这个数组起作用，目标是4。我相信在JS中对象只能包含唯一的键。 mm={ 2 : 0, //2:3将在此处被覆盖 7: 1, 11: 2,}但无论如何，第一个元素不会与自身进行比较，即在这种情况下为2。 - Rayon
在这个问题中，我们考虑所有元素都是唯一的。如果您想处理重复项，则可以添加索引数组。 2：[0,3] 7：1 11：2在检查时，您可以检查所有可能的情况，或者我们可以使用其他方法来解决这个问题。 - himanshu
这并没有回答“所提供的解决方案有什么问题？” - greybeard
1
var twoSum = function(nums, target) {
    
   for(let i=0; i<nums.length; i++){
       for(let j=i+1; j<nums.length; j++){
           if(nums[j] === target - nums[i]){
              return [i, j];
           }
       }
   }
};
2
请不要仅仅发布代码作为答案，还要提供代码的解释以及它是如何解决问题的。带有解释的答案通常更有帮助和更高质量，并且更有可能吸引赞同。 - Hasip Timurtas
这并没有回答“所提供的解决方案有什么问题？” - greybeard
1
您的解决方案符合预期。对于nums = [3, 2 ,4]和target = 6，[0, 0]是所述问题的有效解决方案，因为nums[0] + nums[0] = 3 + 3 = 6。
如果您需要两个不同的索引（在我看来，这不是任务要求），您可以添加一个额外的不等式检查（nums[i] + nums[j] == target && i != j）。
0

另一种高效的解决方案，可以在O(n)时间复杂度下解决这个问题，而不使用嵌套循环。我已经注释了步骤，所以JS开发人员可以轻松理解。以下是我的golang解决方案：

func twoSum(intArray []int, target int) []int {
    response := []int{-1, -1}  // create an array as default response

    if len(intArray) == 0 {  // return default response if the input array is empty
        return response
    }

    listMap := map[int]int{} // create a Map, JS => listMap = new Map()

    for index, value := range intArray { // for loop to fill the map
        listMap[value] = index
    }

    for i, value := range intArray { // for loop to verify if the subtraction is in the map
        result := target - value
        if j, ok := listMap[result]; ok && i != j { // this verify if a property exists on a map in golang. In the same line we verify it i == j.
            response[0] = i
            response[1] = j
            return response
        }
    }

    return response
}
这并没有回答“所提供的解决方案有什么问题？” - greybeard
0
var twoSum = function(nums, target) {
    for(var i=0;i<nums.length;i++){
        for(var j=i+1;j<nums.length;j++){
        temp = nums[i]+nums[j];
        if(temp == target){
            return [i,j]
        }
      }
    }
    
};


console.log(twoSum([15, 7, 11, 2],9))
console.log(twoSum([3, 2, 4],6))
console.log(twoSum([3,3],6))

这个程序运行得非常完美，而且运行时间只有72毫秒，比84毫秒快。

这并没有回答“所提供的解决方案有什么问题？” - greybeard
0
var twoSum = function(nums, target) {
    for (var i = 0; i < nums.length; i++)
    {
        if(  nums.indexOf(target - nums[i]) !== -1)
        {
            return [i , nums.indexOf(target - nums[i])]
        }
    }
};
这并没有回答“所呈现的解决方案有什么问题？” - greybeard
0

为了清晰起见，在内部循环中打印出 a 和 b。这将使您更清楚地了解情况。

var twoSum = function(nums, target) {
var arr=[];
  
for(var a=0;a<nums.length;a++){
    for(var b=1;b<nums.length;b++){
        let c=nums[a]+nums[b];
       
        if(c== target  && a != b){
            
           arr[0]=a;
            arr[1]=b;
            
        }
    }
}   
  return arr;   
};
这并没有回答“所呈现的解决方案有什么问题？” - greybeard
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接