LeetCode 之 JavaScript 解答第一题 —— 两数之和（Two Sum）

k00baa 发布于2019-08-23 16:42 / 2970人阅读

摘要：步骤遍历数组数据，将根据下标和元素值存放到散列表中。目标值减去数组元素差值并在散列表中查找。测试法三一遍哈希表算法思路遍历目标值减去数组元素的差值同时判断该值在散列表中是否存在差值，如果存在，则返回否则将数据加入到散列表中。

Time：2019/4/1
Title:Two Sum
Difficulty: simple
Author:小鹿

题目一：Two Sum

Given an array of integers, return indices of the two numbers such that they add up to a specific target.You may assume that each input would have exactly one solution, and you may not use the same element twice.

问题：给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。你可以假设每种输入只会对应一个答案。但是，你不能重复利用这个数组中同样的元素。

Example:

Given nums = [2, 7, 11, 15], target = 9,

Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1]

Solve:

▉ 法一：暴力破解法

算法思路：用目标值减去数组中的某一个数值，查找差值是否在数组中存在。

/**
 * 步骤：
 * 1）外循环：target 值要一一减去数组中的元素，记录差值
 * 2）内循环：拿着差值去数组中比较判断是否存在
 * 3）如果存在：返回两个元素的下标
 * 4）如果不存在：继续遍历
 *
 * 性能分析：
 * 1）时间复杂度分析：两层 for 循环,所以时间复杂度为 O（n^2）
 * 2）空间复杂度分析：不需要额外的空间，所以空间复杂度为 O（1）
 */
var twoSum = function(nums, target) {
    for(let j = 0;j < nums.length; j++){
        subtract = target - nums[j];
        for(let i = 0;i < nums.length; i++){
            if(nums[i] == subtract && i !== j){
                return [j,i]
            }else{
                continue;
            }
        }
    }
    return false;
};
//测试
const nums = [2,7,11,15];
console.log(twoSum(nums,26));

▉ 法二：两遍哈希表

算法思路：先遍历数组将下标对应的元素存到散列表，然后同目标值减去的值去散列表中查看是否存在。

/**
 * 步骤：
 * 1）遍历数组数据，将根据下标和元素值存放到散列表中。
 * 2）目标值减去数组元素差值并在散列表中查找。
 * 3）如果存在，返回两元素的下标。
 * 4）不存在继续遍历
 *
 * 性能分析：
 * 1）时间复杂度分析：随机访问的时间复杂度为O（1），但是需要遍历所有数据，所以时间复杂度为 O（n）。
 * 2）空间复杂度分析：需要额外的 n 大小的空间存储散列表，空间复杂度为 O(n)。
 */
var twoSum = function(nums, target) {
    var map = new Map();
    for(let i = 0;i < nums.length; i++){
        map.set(nums[i],i)
    }
    for (let j = 0; j < nums.length; j++) {
        substra = target - nums[j];
        if(map.has(substra) && map.get(substra) !== j){
            return [j,map.get(substra)]
        }
    }
}

// 测试
const nums = [2,7,11,15];
console.log(twoSum(nums,9));

▉ 法三：一遍哈希表

算法思路：遍历目标值减去数组元素的差值同时判断该值在散列表中是否存在差值，如果存在，则返回；否则将数据加入到散列表中。

/**
 * 步骤：
 * 1）遍历目标值减去数组元素的差值同时判断该值在散列表中是否存在差值
 * 2）存在该差值，返回该元素下标
 * 3）不存在，将该差值存储到散列表中继续遍历。
 *
 * 性能分析：
 * 1）时间复杂度分析：随机访问的时间复杂度为O（1），但是需要遍历所有数据，所以时间复杂度为 O（n）。
 * 2）空间复杂度分析：需要额外的 n 大小的空间存储散列表，空间复杂度为 O(n)。
 */
var twoSum = function(nums, target) {
    var map = new Map();
    for(let i = 0;i < nums.length; i++){
        substra = target - nums[i];
        if(map.has(substra)){
            return [i,map.get(substra)]
        }
        map.set(nums[i],i)
    }
    return false;
}

// 测试
const nums = [2,7,11,15];
console.log(twoSum(nums,26));

▉ 总结：

1、涉及到查找、判断是否存在，相关的数据结构有散列表、平衡二叉树、二分查找、跳表、二叉查找树。

2、使用数据结构的时候注意适用条件。

3、注意对时间复杂度、空间复杂度的优化策略。

欢迎一起加入到 LeetCode 开源 Github 仓库，可以向 me 提交您其他语言的代码。在仓库上坚持和小伙伴们一起打卡，共同完善我们的开源小仓库！
Github：https://github.com/luxiangqia...

欢迎关注我个人公众号：「一个不甘平凡的码农」，记录了自己一路自学编程的故事。

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/103162.html

LeetCode 之 JavaScript 解答第二题 —— 两数相加（Add Two Number

摘要：多位数加多位数，反转链表转化整数，如果整数相加，可能会溢出，此方法行不通。直接进行位数运算，两链表每取出一个就做运算，将结果放入到新链表中。求和运算会出现额外的进位一般进位与最高位进位两种情况。两位数取模运算。 Time：2019/4/2Title: ADD Two NumbersDifficulty: mediumAuthor:小鹿公众号：一个不甘平凡的码农。题目二：ADD Two...

Sunxb 2019-08-23 16:43 评论0 收藏0
前端 | 每天一个 LeetCode

摘要：在线网站地址我的微信公众号完整题目列表从年月日起，每天更新一题，顺序从易到难，目前已更新个题。这是项目地址欢迎一起交流学习。这篇文章记录我练习的 LeetCode 题目，语言 JavaScript。在线网站：https://cattle.w3fun.com GitHub 地址：https://github.com/swpuLeo/ca...我的微信公众号： showImg(htt...

张汉庆 2019-08-23 13:42 评论0 收藏0
LeetCode - 001 - 两数之和（two-sum）

摘要：解法返回目录解题代码执行测试解题思路使用双重循环破解。解法返回目录解题代码执行测试知识点遍历数组，返回遍历项，返回当前索引。 Create by jsliang on 2019-05-16 22:19:13 Recently revised in 2019-05-17 14:22:40 Hello 小伙伴们，如果觉得本文还不错，记得给个 star ，小伙伴们的 star 是我持续更新的动...

habren 2019-05-23 17:27 评论0 收藏0
[Leetcode] Two Sum 两数和

摘要：如果存在该差值，说明存在两个数之和是目标和。而哈希表方法中的则可以换成。如果要求的不是两个数和和，而是找两个数之差为特定值的配对呢同样用哈希表可以解决。 Two Sum Given an array of integers, find two numbers such that they add up to a specific target number.The function t...

pkhope 2019-08-14 12:18 评论0 收藏0
LeetCode 167：两数之和 II - 输入有序数组 Two Sum II - Input a

摘要：公众号爱写给定一个已按照升序排列的有序数组，找到两个数使得它们相加之和等于目标数。函数应该返回这两个下标值和，其中必须小于。示例输入输出解释与之和等于目标数。公众号：爱写bug（ID：icodebugs）给定一个已按照升序排列的有序数组，找到两个数使得它们相加之和等于目标数。函数应该返回这两个下标值 index1 和 index2，其中 index1 必须小于 index2。...

张春雷 2019-08-16 18:29 评论0 收藏0