本文共 1289 字，大约阅读时间需要 4 分钟。

两数之和

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

你可以假设每种输入只会对应一个答案。但是，你不能重复利用这个数组中同样的元素。

示例:

解答

一、暴力法 时间复杂度：O(n²)

思路：使用双层for循环，外层遍历数组，寻找当前元素与target的差值，内层循环遍历整个数组，寻找有没有值与差值相同。如果找到，返回两个元素的下标。

let twoSum = function(nums, target) {
       for (let i = 0; i < nums.length; i++) {
           let d_value = target - nums[i];        for (let j = i + 1; j < nums.length; j++) {
               if(nums[j] === d_value)                return [i,j];        }    }};console.log(twoSum([1,2,3,4,5],8))

运行结果：

二、数组法 时间复杂度：O(n)

思路：使用一层循环遍历整个数组，首先计算当前元素与target的差值d_value ，然后以d_value 为下标到数组result中寻找。如果有值，返回下标；如果没有找到，将当前元素存入result中（存入下标和值均为d_value）。

在这个方法中，最终的result数组中，有很多空元素位置。只有以nums数组中的元素为下标的地方有值，且值为nums数组中的元素本身。

let twoSum = function(nums, target) {
       let result = [];    for(let i=0;i

运行结果：

三、ES6 新语法，Map 时间复杂度：O(n)

一个Map类似于一个对象，但相对于对象更加强大，其键可以是多种类型

通过map可以更加方便的设置、获取、比较值

let twoSum = (nums, target) => {
       let targetMap = new Map();    for (let i = 0; i < nums.length; i++) {
           const key = target - nums[i];        if (targetMap.has(key)) {
               return [targetMap.get(key), i]        }        targetMap.set(nums[i], i)    }};console.log(twoSum([13,26,4,14,24],28));

运行结果：

转载地址：https://kaisarh.blog.csdn.net/article/details/105339287 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！