文章目錄

兩數之和
- 一、題目
- 二、菜鳥解法
- 三、優化解
- - 1.暴力解法【線性查找】
  - 2.優化【哈希查找】
  - 3.進一步優化【哈希查找】
- 四、知識拓展 --- JavaScript中`map`的用法

兩數之和

一、題目

給定一個整數陣列 nums 和一個整數目標值target，請你在該陣列中找出和為目標值target 的那兩個整數，并回傳它們的陣列下標，

你可以假設每種輸入只會對應一個答案，但是，陣列中同一個元素在答案里不能重復出現，

你可以按任意順序回傳答案，

示例 1：

輸入：nums = [2,7,11,15], target = 9
輸出：[0,1]
解釋：因為 nums[0] + nums[1] == 9 ，回傳 [0, 1] ，

示例 2：

輸入：nums = [3,2,4], target = 6
輸出：[1,2]

示例 3：

輸入：nums = [3,3], target = 6
輸出：[0,1]

提示：

2 <= nums.length <= 104
-109 <= nums[i] <= 109
-109 <= target <= 109
只會存在一個有效答案

進階： 你可以想出一個時間復雜度小于 O(n² ) 的演算法嗎？

來源：力扣（LeetCode）

二、菜鳥解法

1.思路
利用雙重for回圈，將陣列里的值依次相加，直至等于目標值
2.代碼

var twoSum = function(nums, target) {
    var result=[]
    
    for(var i=0;i<nums.length;i++){
        for(var j=i+1;j<nums.length;j++){
            if(nums[i]+nums[j] == target){
                result[0]=i;
                result[1]=j;
                break                
            }
        } 
    }
          return result
};

3.執行結果
在這里插入圖片描述

三、優化解

一個刷題套路：先暴力，然后優化，繼續優化，最后追求程式的極致性能
三個優化演算法的應用：二分查找、哈希查找和雙指標技巧

1.暴力解法【線性查找】

// 時間復雜度：O(n^2)
// 空間復雜度：O(1)
var twoSum = function(nums, target) {
    if(!nums || !nums.length) return []

    for(let i=0;i < nums.length;i++){
        let x = nums[i];
        for(let j=i+1; j< nums.length; j++){
            if(nums[j] == target - x){
                return [i,j]
            }
        }
    }
};

在這里插入圖片描述
注：雖然相比我自己寫的代碼，執行用時和記憶體消耗并沒有提高，但顯然這種寫法更簡潔、易懂

2.優化【哈希查找】

// 時間復雜度：O(n)
// 空間復雜度：O(n)
// 空間換時間
var twoSum = function(nums, target) {
    const map = new Map()
    nums.forEach((num,i)=> map.set(num,i))

    for(let i=0;i < nums.length;i++){
        const x = nums[i];
        if(map.has(target - x)){
            const index=map.get(target - x)
            if(i != index) return [i,index]
        }
    }
};

在這里插入圖片描述

3.進一步優化【哈希查找】

兩次遍歷->一次遍歷

// 時間復雜度：O(n)
// 空間復雜度：O(n)
// 空間換時間
var twoSum = function(nums, target) {
    const map = new Map()

    for(let i=0;i < nums.length;i++){
        const x = nums[i];
        if(map.has(target - x)){
            const index=map.get(target - x)
             return [index,i]
        }
        map.set(x,i)
    }
};

在這里插入圖片描述

四、知識拓展 — JavaScript中`map`的用法

宣告

var map = new Map();

設值

map.set("key","value");

取值

map.get("key");

判斷key是否存在

map.has("key");

洗掉key

map.delete("key");

轉載請註明出處，本文鏈接：https://www.uj5u.com/qianduan/293987.html

標籤：其他

上一篇：toString與valueOf區別

下一篇：Nodejs學習之路

01-兩數之和