Title link: leetcode-cn.com/problems/tw…

Method one: violence method

The first thing that comes to mind is that two loops are nested, going through each element x, and looking for a target element with a value equal to target-x.

/** * @param {number[]} nums * @param {number} target * @return {number[]} */
var twoSum = function(nums, target) {
    for (let i = 0; i < nums.length; i++) {
        for (let j = i + 1; j < nums.length; j++) {
            if (target - nums[i] === nums[j]) {
                return[i, j]; }}}console.log("No two sum solution");
};
Copy the code
  • Time complexity: O(n^2)
  • Space complexity: O(1)

Method two: run the hash table twice

To optimize the runtime complexity, we can use hash tables. A simple implementation uses two iterations. In the first iteration, we add the value of each element and its index to the table. Then, in the second iteration, we check whether target-nums [I], the target element corresponding to each element, exists in the table. Note that the target element cannot be nums[I] itself!

/** * @param {number[]} nums * @param {number} target * @return {number[]} */
var twoSum = function(nums, target) {
    // create a hash table
    var map = new Map(a);for (let i = 0; i < nums.length; i++) {
        map.set(nums[i], i);
    }
    for (let j = 0; j < nums.length; j++) {
        let complement = target - nums[j];
        if(map.has(complement) && map.get(complement) ! == j) {return[j, map.get(complement)]; }}console.log("No two sum solution");
};
Copy the code
  • Time complexity: O(n)
  • Space complexity: O(n)

Method three: Run the hash table again

We can do this by going through the hash table, iterating over and inserting elements into the table, and checking to see if the target element for the current element already exists in the table. If it exists, we have found the counterpart and returned it immediately.

/** * @param {number[]} nums * @param {number} target * @return {number[]} */
var twoSum = function(nums, target) {
    // create a hash table
    var map = new Map(a);for (let i = 0; i < nums.length; i++) {
        let complement = target - nums[i];
        if (map.has(complement)) {
            return [map.get(complement), i];
        }
        map.set(nums[i], i);
    }
    console.log("No two sum solution");
};
Copy the code
  • Time complexity: O(n)
  • Space complexity: O(n)

More antithesis

Please follow: github.com/leviding/le…

Add WeChatimlevidingFill in the verification informationalgorithmJoin JavaScript algorithm group, punch LeetCode every day.

My level is limited, welcome to exchange and share your ideas, welcome big guy criticism and correction.