【LeetCode with JavaScript】1.Two Sum

痛定思痛。 2022-05-24 08:41 171阅读 0赞

原题网址：[https://leetcode.com/problems/two-sum/][https_leetcode.com_problems_two-sum]  
难度：Easy

#### 题目 ####

给定一个整数数组和一个目标值，找出数组中和为目标值的两个数。

你可以假设每个输入只对应一种答案，且同样的元素不能被重复利用。

**Example:**

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

#### 思路一 ####

--------------------

遍历nums，同时使用 indexOf()，查找是否存在 target - nums\[i\]，存在则返回结果，不存在继续遍历。下面是代码：

Your runtime beats 30.05 % of javascript submissions。  
运行时间：180ms，还有提升的空间。

#### 思路二 ####

--------------------

创建一个新对象 exist，遍历 nums，将 nums\[i\] 存入 `exist[nums[i]]`，同时判断 `exist[target - nums[i]]` 是否存在，存在返回结果，不存在继续遍历。  
  思路一的 indexOf() 时间复杂度是 O(n)，故思路一时间复杂度为 O(n\*n)，而 JavaScript 的对象属性查找是哈希查找，时间复杂的是 O(1)，思路二的时间复杂度为 O(n)。下面是代码：

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

Your runtime beats 99.96 % of javascript submissions.  
运行时间：52ms，clear！

[https_leetcode.com_problems_two-sum]: https://leetcode.com/problems/two-sum/