LeetCode.1 兩數之和(Two Sum)(JS)

Gu_Yan 發布于2019-08-23 16:15 / 1887人閱讀

摘要：開坑，以后每周刷一兩道一題目兩數之和給定一個整數數組和一個目標值，請你在該數組中找出和為目標值的那兩個整數，并返回他們的數組下標。但是，你不能重復利用這個數組中同樣的元素。

開坑，以后每周刷一兩道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%多的提交記錄，還有繼續的勇氣

四、路漫漫其修遠兮

GPU云服務器云服務器 two-sum two.js cdn 之和兩數相

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/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