LeetCode.1 两数之和(Two Sum)(JS)

Gu_Yan 发布于2019-08-23 16:15 / 1765人阅读

摘要：开坑，以后每周刷一两道一题目两数之和给定一个整数数组和一个目标值，请你在该数组中找出和为目标值的那两个整数，并返回他们的数组下标。但是，你不能重复利用这个数组中同样的元素。

开坑，以后每周刷一两道LeetCode

一、题目

两数之和：

给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。
你可以假设每种输入只会对应一个答案。但是，你不能重复利用这个数组中同样的元素。
示例
给定 nums = [2, 7, 11, 15], target = 9
因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]

二、优秀答案

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */
var twoSum = function(nums, target) {
    const comp = {};
    for(let i=0; i=0){
            return [ comp[target - nums[i] ] , i]
        }
        comp[nums[i]] = i
    }
};

遍历数组，定义一个对象,
对象属性的key是顺序遍历中数组项的value，对象属性的value是数组项的下标

comp[target-nums[i]] = i

一旦存在对象中target-nums[i]属性的值(即数组项的下标)大于0，即存在数组中两数之和等于target

if(comp[target - nums[i] ]>=0){
    return [ comp[target - nums[i] ] , i]
}

我还能说什么，map掌握得炉火纯青。

三、我的答案

~~公开处刑现场~~

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */
var twoSum = function (nums, target) {
      function isEqualToTarget(num1, num2) {
        if (num1 + num2 === target) {
          return true
        } else {
          return false
        }
      }

      function findTargetItem(arr, oldArr) {
        for (let i = 0; i < arr.length - 1; i++) {
          for (let j = i + 1; j < arr.length; j++) {
            if (isEqualToTarget(arr[i], arr[j])) {
              return [oldArr.indexOf(arr[i]), oldArr.length - 1 - oldArr.reverse().indexOf(arr[j])]
            }
          }
        }
      }
      const oldArray = nums.slice(0)
      nums.sort((a, b) => a - b)
      let tailIndex = nums.findIndex((value, index) => {
        return value >= target - nums[0] && index !== 0
      })
      if (tailIndex === -1) { // [5, 7, 11, 12] 18
        return findTargetItem(nums, oldArray)
      } else if (isEqualToTarget(nums[0], nums[tailIndex])) {
        return [oldArray.indexOf(nums[0]), oldArray.length - 1 - oldArray.reverse().indexOf(nums[tailIndex])]
      } else {
        nums.length = tailIndex + 1
        return findTargetItem(nums, oldArray)
      }
    };

当时写的主要想法依然是暴力遍历，只不过做了一丁点儿优化

nums.sort((a, b) => a - b)
let tailIndex = nums.findIndex((value, index) => {
    return value >= target - nums[0] && index !== 0
})

先从小到大排序，然后去掉与数组最小值相加大于target的值。
这个过程算优化吧/捂脸

好歹战胜70%多的提交记录，还有继续的勇气

四、路漫漫其修远兮

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

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

Leetcode 1：两数之和

摘要：给定一个整数数组和一个目标值，请你在该数组中找出和为目标值的那两个整数，并返回他们的数组下标。示例给定因为所以返回方法，暴力解法。函数可以将一个数组转化为一个从开始，值为数组对应元素的字典。给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那两个整数，并返回他们的数组下标。你可以假设每种输入只会对应一个答案。但是，你不能重复利用这个数组中...

Taste 2019-07-31 11:24 评论0 收藏0
LeetCode 167：两数之和 II - 输入有序数组 Two Sum II - Input a

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

张春雷 2019-08-16 18:29 评论0 收藏0
LeetCode 167：两数之和 II - 输入有序数组 Two Sum II - Input a

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

Me_Kun 2019-07-31 11:26 评论0 收藏0
两数之和问题各变种多解法小结

摘要：两数之和问题各变种多解法小结声明文章均为本人技术笔记，转载请注明出处两数之和等于题目大意给出未排序数组和指定目标，返回数组中两数之和的组合元素下标要求下标从开始，而且，保证题目中有且只有个可行解解法暴力时间复杂度求解解题思路暴力二重循环求解两数之和问题各变种多解法小结声明文章均为本人技术笔记，转载请注明出处：[1] https://segmentfault.com/u/yzwal...

lentoo 2019-08-16 10:34 评论0 收藏0
6-9月技术文章汇总

摘要：分布式的管理和当我在谈论架构时我在谈啥状态码详解无状态协议和请求支持哪些方法分层协议栈有哪些数据结构运用场景说说你常用的命令为什么要有包装类面向对象的特征是啥是啥有什么好处系统设计工程在线诊断系统设计与实现索引背后的数据结构及算法原理软技能 HTTP 【HTTP】分布式session的管理【HTTP】Cookie和Session 【HTTP】当我在谈论RestFul架构时我在谈啥？...

miya 2019-07-30 18:03 评论0 收藏0