【LeetCode 1】两数之和（多种解法）

短命女 2023-02-16 00:53 15阅读 0赞

### 题目描述 ###

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

你可以假设每种输入只会对应一个答案。但是，数组中同一个元素不能使用两遍。

示例:

给定 nums = [2, 7, 11, 15], target = 9
    
    因为 nums[0] + nums[1] = 2 + 7 = 9
    所以返回 [0, 1]

### 解题思路 ###

这是一个简单题，我们很容易想到使用两层循环来解决这个问题，但是两层循环的复杂度为**O（n2）**，我们可以考虑能否换一种思路，减小复杂度。

这里我们使用一个`map`对象来储存遍历过的数字以及对应的索引值。我们在这里使用减法进行计算

*  计算`target`和第一个数字的差，并记录进`map`对象中，其中两数差值作为`key`，其索引值作为value。
 *  再计算第二个数字与`target`的差，并与`map`对象中的数值进行对比，若相同，直接返回，如果没有相同值，就将这个差值也存入`map`对象中。
 *  重复第二步，直到找到目标值。

这里有一个小知识点：

JavaScript 对象取值有以下两种方式，这次我们使用第二种：

var obj = { name:"hello"};
    var v1 = obj.name;//使用点的方式
    var v2 = obj["name"];//使用中括号的方式

### 代码实现 ###

先来附上两层循环遍历的代码：

/** * @param {number[]} nums * @param {number} target * @return {number[]} */
    var twoSum = function(nums, target) { 
        var len=nums.length;
         for(var i=0;i<len;i++){ 
             for(var j=0;j<len;j++){ 
                 if(nums[i]+nums[j] == target&&i!=j){ 
                     return [i,j];
                 }
             }
         }
    };

使用map对象存储方法：

/** * @param {number[]} nums * @param {number} target * @return {number[]} */
    var twoSum = function(nums, target) { 
        const maps = { }
        const len = nums.length    
    
        for(let i=0;i<len;i++) { 
            if(maps[target-nums[i]]!==undefined) { 
                return [maps[target - nums[i]], i]
            }
            maps[nums[i]]=i
        }
    };

### 提交结果 ###

第二种方法的提交结果：  
![ia][]

[ia]: https://img-blog.csdnimg.cn/20200606232504574.png