LeetCode 之 JavaScript 解答第一題 —— 兩數之和（Two Sum）

k00baa 發布于2019-08-23 16:42 / 2971人閱讀

摘要：步驟遍歷數組數據，將根據下標和元素值存放到散列表中。目標值減去數組元素差值并在散列表中查找。測試法三一遍哈希表算法思路遍歷目標值減去數組元素的差值同時判斷該值在散列表中是否存在差值，如果存在，則返回否則將數據加入到散列表中。

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...

歡迎關注我個人公眾號：「一個不甘平凡的碼農」，記錄了自己一路自學編程的故事。

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

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