Two-sum Leetcode explanation, Hashmap, Javascript

huangapple go评论83阅读模式
英文:

Two-sum Leetcode explanation, Hashmap, Javascript

问题

我只翻译代码部分:

var twoSum = function(nums, target) {
  let hash = {};

  for(let i = 0; i < nums.length; i++) {
    const n = nums[i];
    if(hash[target - n] !== undefined) {
      return [hash[target - n], i];
    }
    hash[n] = i;
  }
  return [];
}
英文:

Im just wondering who can explain the algorithm of this solution step by step. I dont know how hashmap works. Can you also give a basic examples using a hashmap for me to understand this algorithm. Thank you!

var twoSum = function(nums, target) {
  let hash = {};

  for(let i = 0; i &lt; nums.length; i++) {
    const n = nums[i];
    if(hash[target - n] !== undefined) {
      return [hash[target - n], i];
    }
    hash[n] = i;
  }
  return [];
}

答案1

得分: 18

你的代码接受一个数字数组和一个目标数字/总和,然后返回数组中两个相加等于目标数字/总和的数字的索引。

考虑一个数字数组,例如 [1, 2, 3] 和一个目标数字 5。你的任务是找到在这个数组中相加得到 5 的两个数字。解决这个问题的一种方法是遍历数组中的每个数字,并问自己:"我已经在我的数组中看到了哪个数字,我可以将它与当前数字相加以达到我的 target 总和?"

首先,我们遍历示例数组 [1, 2, 3],从索引 0 开始,当前数字是 1。目前,我们还没有看到任何可以与 1 相加得到目标 5 的数字,因为我们还没有遍历过任何数字。

因此,到目前为止,我们已经遇到数字 1,它位于索引 0。这在哈希映射(对象)中存储为 { '1': 0 },其中键是数字,值(0)是它出现的索引。对象的目的是存储我们已经看到的数字以及它们出现的索引。

接下来,循环继续到索引 1,当前数字为 2。现在,我们可以问自己这个问题:在我的数组中,是否有一个已经看到的数字,我可以将它添加到当前数字 2 以达到目标总和 5?要获得将当前数字添加到目标所需的数量,可以通过 target - currentNumber 来获得。在这种情况下,当前数字是 2,所以我们需要添加 3 来达到目标总和 5。使用哈希映射/对象,我们可以检查是否已经看到数字 3。为此,我们可以尝试通过 obj[target - currentNumber] 访问键 3。目前,我们的对象只有键 1,所以当我们尝试访问键 3 时,会得到 undefined。这意味着我们还没有看到数字 3,所以到目前为止,我们不能将任何东西添加到 2 以达到目标。

因此,现在我们的对象/哈希映射看起来像这样:{ '1': 0, '2': 1 },因为我们已经看到数字 1,它位于索引 0,还看到数字 2,它位于索引 1

最后,我们到达数组的最后一个数字,位于索引 2。数组的索引 2 包含数字 3。现在,我们再次问自己这个问题:是否有一个我们已经看到的数字,我们可以将它添加到 3(当前数字)以达到目标总和?我们需要将 3 添加到 3 以达到目标数字 5,我们可以检查我们的对象,看看是否已经在数组中看到数字 2。为此,我们可以使用 obj[target - currentNumber] 来获取存储在键 2 处的值,该值存储了索引 1。这意味着数字 2 确实存在于数组中,因此我们可以将其添加到 3 以达到目标。由于值在对象中,我们现在可以返回我们的结果,即已看到的数字发生的索引以及当前数字的索引。

总之,对象用于跟踪数组中先前看到的所有数字以及它们出现的索引。

这是运行你的代码的示例。它返回 [1, 2],因为索引 12 处的数字可以相加得到目标总和 5

希望这可以帮助你理解代码的工作原理。如果你有其他问题,请随时提出。

英文:

Your code takes an array of numbers and a target number/sum. It then returns the indexes in the array for two numbers which add up to the target number/sum.

Consider an array of numbers such as [1, 2, 3] and a target of 5. Your task is to find the two numbers in this array which add to 5. One way you can approach this problem is by looping over each number in your array and asking yourself "Is there a number (which I have already seen in my array) which I can add to the current number to get my target sum?".

Well, if we loop over the example array of [1, 2, 3] we first start at index 0 with the number 1. Currently, there are no numbers which we have already seen that we can add with 1 to get our target of 5 as we haven't looped over any numbers yet.

So, so far, we have met the number 1, which was at index 0. This is stored in the hashmap (ie object) as {&#39;1&#39;: 0}. Where the key is the number and the value (0) is the index it was seen at. The purpose of the object is to store the numbers we have seen and the indexes they appear at.

Next, the loop continues to index 1, with the current number being 2. We can now ask ourselves the question: Is there a number which I have already seen in my array that I can add to my current number of 2 to get the target sum of 5. The amount needed to add to the current number to get to the target can be obtained by doing target-currentNumber. In this case, we are currently on 2, so we need to add 3 to get to our target sum of 5. Using the hashmap/object, we can check if we have already seen the number 3. To do this, we can try and access the object 3 key by doing obj[target-currentNumber]. Currently, our object only has the key of &#39;1&#39;, so when we try and access the 3 key you'll get undefined. This means we haven't seen the number 3 yet, so, as of now, there isn't anything we can add to 2 to get our target sum.

So now our object/hashmap looks like {&#39;1&#39;: 0, &#39;2&#39;: 1}, as we have seen the number 1 which was at index 0, and we have seen the number 2 which was at index 1.

Finally, we reach the last number in your array which is at index 2. Index 2 of the array holds the number 3. Now again, we ask ourselves the question: Is there a number we have already seen which we can add to 3 (our current number) to get the target sum?. The number we need to add to 3 to get our target number of 5 is 2 (obtained by doing target-currentNumber). We can now check our object to see if we have already seen a number 2 in the array. To do so we can use obj[target-currentNumber] to get the value stored at the key 2, which stores the index of 1. This means that the number 2 does exist in the array, and so we can add it to 3 to reach our target. Since the value was in the object, we can now return our findings. That being the index of where the seen number occurred, and the index of the current number.

In general, the object is used to keep track of all the previously seen numbers in your array and keep a value of the index at which the number was seen at.

Here is an example of running your code. It returns [1, 2], as the numbers at indexes 1 and 2 can be added together to give the target sum of 5:

<!-- begin snippet: js hide: false console: true babel: false -->

<!-- language: lang-js -->

const twoSum = function(nums, target) {
  const hash = {}; // Stores seen numbers: {seenNumber: indexItOccurred}

  for (let i = 0; i &lt; nums.length; i++) { // loop through all numbers
    const n = nums[i]; // grab the current number `n`.
    if (hash[target - n] !== undefined) { // check if the number we need to add to `n` to reach our target has been seen:
      return [hash[target - n], i]; // grab the index of the seen number, and the index of the current number
    }
    hash[n] = i; // update our hash to include the. number we just saw along with its index.
  }
  return []; // If no numbers add up to equal the `target`, we can return an empty array
}

console.log(twoSum([1, 2, 3], 5)); // [1, 2]

<!-- end snippet -->

A solution like this might seem over-engineered. You might be wondering why you can't just look at one number in the array, and then look at all the other numbers and see if you come across a number that adds up to equal the target. A solution like that would work perfectly fine, however, it's not very efficient. If you had N numbers in your array, in the worst case (where no two numbers add up to equal your target) you would need to loop through all of these N numbers - that means you would do N iterations. However, for each iteration where you look at a singular number, you would then need to look at each other number using a inner loop. This would mean that for each iteration of your outer loop you would do N iterations of your inner loop. This would result in you doing N*N or N<sup>2</sup> work (O(N<sup>2</sup>) work). Unlike this approach, the solution described in the first half of this answer only needs to do N iterations over the entire array. Using the object, we can find whether or not a number is in the object in constant (O(1)) time, which means that the total work for the above algorithm is only O(N).

For further information about how objects work, you can read about bracket notation and other property accessor methods here.

答案2

得分: 0

以下是您提供的内容的中文翻译:

你可能想要查看这种方法,它对我来说非常有效,我已经写了很多评论来帮助初学者更好地理解。

let nums = [2, 7, 11, 15];
let target = 9;

function twoSums(arr, t){
    let num1;
    //创建第一个数字的变量
    let num2;
    //创建第二个数字的变量
    let index1;
    //创建第一个数字的索引变量
    let index2;
    //创建第二个数字的索引变量
    for(let i = 0;  i < arr.length; i++){
        //使用循环遍历数组元素
        num1 = arr[i];
        //将数组迭代值i分配给num1变量
        //例如:num1 = arr[0],其值为2
        num2 = t - num1; 
        //获取目标值t与num1中的数字之间的差值
        //例如:t(9) - num1(2) = 7;
        if(arr.includes(num2)){
            //检查num2数字是否包含在数组中
            index1 = arr.indexOf(num2);
            //如果是,获取num2值(例如7)在数组中的索引
            //例如:数组中7的索引是1
            index2 = arr.indexOf(num1)
            //获取num1值(例如2)在数组中的索引,2在数组中的索引是0
        }
    }
    return(`[${index1}, ${index2}]`);
    //以方括号形式返回索引。您可以选择创建一个数组并将值推入其中,但要考虑空间复杂性。
}

console.log(twoSums(nums, target));
//调用函数。请记住,我们已经在顶部声明了这些值。

//在我看来,这种方法是最佳的,它同时考虑了时间复杂度和空间复杂度,将它们降到最低。

//时间复杂度:O(n)

请注意,以上是您提供的代码部分的中文翻译。

英文:

You may want to check out this method, it worked so well for me and I have written a lot of comments on it to help even a beginner understand better.

<!-- begin snippet: js hide: false console: true babel: false -->

<!-- language: lang-js -->

let nums = [2, 7, 11, 15];
let target = 9;

function twoSums(arr, t){
    let num1;
    //create the variable for the first number
    let num2;
    //create the variable for the second number
    let index1;
    //create the variable for the index of the first number
    let index2;
    //create the variable for the index of the second number
    for(let i = 0;  i &lt; arr.length; i++){
        //make a for loop to loop through the array elements
        num1 = arr[i];
        //assign the array iteration, i, value to the num1 variable
        //eg: num1 = arr[0] which is 2
        num2 = t - num1; 
        //get the difference between the target and the number in num1.
        //eg: t(9) - num1(2) = 7;
        if(arr.includes(num2)){
            //check to see if the num2 number, 7, is contained in the array;
            index1 = arr.indexOf(num2);
            //if yes get the index of the num2 value, 7, from the array, 
            // eg: the index of 7 in the array is 1;
            index2 = arr.indexOf(num1)
            //get the index of the num1 value, which is 2, theindex of 2 in the array is 0;
        }
    }
    return(`[${index1}, ${index2}]`);
    //return the indexes in block parenthesis. You may choose to create an array and push the values into it, but consider space complexities.
}

console.log(twoSums(nums, target));
//call the function. Remeber we already declared the values at the top already.


//In my opinion, this method is best, it considers both time complexity and space complexityat its lowest value.

//Time complexity: 0(n)

<!-- end snippet -->

答案3

得分: -3

function twoSum(numbers, target) {
  for (let i = 0; i < numbers.length; i++) {
    for (let j = i + 1; j < numbers.length; j++) {
      if (numbers[i] + numbers[j] === target) {
        return [numbers.indexOf(numbers[i]), numbers.lastIndexOf(numbers[j])];
      }
    }
  }
}
英文:
function twoSum(numbers, target) {
  for (let i = 0; i &lt; numbers.length; i++) {
    for (let j = i + 1; j &lt; numbers.length; j++) {
      if (numbers[i] + numbers[j] === target) {
        return [numbers.indexOf(numbers[i]), numbers.lastIndexOf(numbers[j])];
      }
    }
  }
}

huangapple
  • 本文由 发表于 2020年1月6日 21:26:57
  • 转载请务必保留本文链接:https://go.coder-hub.com/59612976.html
匿名

发表评论

匿名网友

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

确定