关于javascript:Leetcode两数之和

起源：力扣（LeetCode）

给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 的那 两个 整数，并返回它们的数组下标。

你能够假如每种输出只会对应一个答案。然而，数组中同一个元素在答案里不能反复呈现。

你能够按任意程序返回答案。

示例 1：

 输出：nums = [2,7,11,15], target = 9
输入：[0,1]
解释：因为 nums[0] + nums[1] == 9，返回 [0, 1]。

示例 2：

 输出：nums = [3,2,4], target = 6
输入：[1,2]

示例 3：

 输出：nums = [3,3], target = 6
输入：[0,1]

提醒：

• 2 <= nums.length <= 103
• -109 <= nums[i] <= 109
• -109 <= target <= 109
• 只会存在一个无效答案

形式一：暴力迭代

暴力迭代就是两层遍历，循环迭代每两个数都进行匹配

JavaScript

var twoSum = function(nums, target) {for (let i = 0; i < nums.length - 1; i++) {for (let j = i+1; j < nums.length; j++) {if (nums[i] + nums[j] === target) {return [i, j]
            }
        }        
    }
    return [];};

• 工夫复杂度：O($n*n$)
• 空间复杂度：O(1)

python 版本

class Solution(object):
    def twoSum(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[int]
        """
        for i in range(len(nums)):
            for j in range(i+1, len(nums)):
                if (nums[i] + nums[j] == target):
                    return [i, j]
        return [];

形式二：哈希表

就是用一个对象来存储元素和其索引

• 每一次用目标值 target – 以后元素，判断其值是否在哈希表中
• 若存在，即返回哈希表中对应的值和以后元素的索引
• 否则，将以后元素机器索引存储到哈希表中

这样就只须要一次遍历，毛病就是须要额定保护一个哈希表

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */
var twoSum = function(nums, target) {let obj = {};
    for (let i = 0; i <nums.length; i++) {if (parseInt(target - nums[i]) in obj) {return [obj[target - nums[i]], i];
        }
        obj[nums[i]] = i;
    }
    return [];};

• 工夫复杂度：O(n)
• 空间复杂度：O(n)

python

class Solution(object):
    def twoSum(self, nums, target):
        hashtable = dict()
        for key, value in enumerate(nums):
            if target-value in hashtable:
                return [hashtable[target - value], key]
            hashtable[value] = key
        return []