成人国产在线小视频_日韩寡妇人妻调教在线播放_色成人www永久在线观看_2018国产精品久久_亚洲欧美高清在线30p_亚洲少妇综合一区_黄色在线播放国产_亚洲另类技巧小说校园_国产主播xx日韩_a级毛片在线免费

資訊專欄INFORMATION COLUMN

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

k00baa / 2983人閱讀

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

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.
問(wèn)題：給定一個(gè)整數(shù)數(shù)組 nums 和一個(gè)目標(biāo)值 target，請(qǐng)你在該數(shù)組中找出和為目標(biāo)值的那 兩個(gè) 整數(shù)，并返回他們的數(shù)組下標(biāo)。你可以假設(shè)每種輸入只會(huì)對(duì)應(yīng)一個(gè)答案。但是，你不能重復(fù)利用這個(gè)數(shù)組中同樣的元素。

Example:

Given nums = [2, 7, 11, 15], target = 9,

Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1]

Solve:

▉ 法一：暴力破解法
算法思路：用目標(biāo)值減去數(shù)組中的某一個(gè)數(shù)值，查找差值是否在數(shù)組中存在。
/**
 * 步驟：
 * 1）外循環(huán)：target 值要一一減去數(shù)組中的元素，記錄差值
 * 2）內(nèi)循環(huán)：拿著差值去數(shù)組中比較判斷是否存在
 * 3）如果存在：返回兩個(gè)元素的下標(biāo)
 * 4）如果不存在：繼續(xù)遍歷
 *
 * 性能分析：
 * 1）時(shí)間復(fù)雜度分析：兩層 for 循環(huán),所以時(shí)間復(fù)雜度為 O（n^2）
 * 2）空間復(fù)雜度分析：不需要額外的空間，所以空間復(fù)雜度為 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;
};
//測(cè)試
const nums = [2,7,11,15];
console.log(twoSum(nums,26));
▉ 法二：兩遍哈希表
算法思路：先遍歷數(shù)組將下標(biāo)對(duì)應(yīng)的元素存到散列表，然后同目標(biāo)值減去的值去散列表中查看是否存在。
/**
 * 步驟：
 * 1）遍歷數(shù)組數(shù)據(jù)，將根據(jù)下標(biāo)和元素值存放到散列表中。
 * 2）目標(biāo)值減去數(shù)組元素差值并在散列表中查找。
 * 3）如果存在，返回兩元素的下標(biāo)。
 * 4）不存在繼續(xù)遍歷
 *
 * 性能分析：
 * 1）時(shí)間復(fù)雜度分析：隨機(jī)訪問(wèn)的時(shí)間復(fù)雜度為O（1），但是需要遍歷所有數(shù)據(jù)，所以時(shí)間復(fù)雜度為 O（n）。
 * 2）空間復(fù)雜度分析：需要額外的 n 大小的空間存儲(chǔ)散列表，空間復(fù)雜度為 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)]
        }
    }
}

// 測(cè)試
const nums = [2,7,11,15];
console.log(twoSum(nums,9));
▉ 法三：一遍哈希表
算法思路：遍歷目標(biāo)值減去數(shù)組元素的差值同時(shí)判斷該值在散列表中是否存在差值，如果存在，則返回；否則將數(shù)據(jù)加入到散列表中。
/**
 * 步驟：
 * 1）遍歷目標(biāo)值減去數(shù)組元素的差值同時(shí)判斷該值在散列表中是否存在差值
 * 2）存在該差值，返回該元素下標(biāo)
 * 3）不存在，將該差值存儲(chǔ)到散列表中繼續(xù)遍歷。
 *
 * 性能分析：
 * 1）時(shí)間復(fù)雜度分析：隨機(jī)訪問(wèn)的時(shí)間復(fù)雜度為O（1），但是需要遍歷所有數(shù)據(jù)，所以時(shí)間復(fù)雜度為 O（n）。
 * 2）空間復(fù)雜度分析：需要額外的 n 大小的空間存儲(chǔ)散列表，空間復(fù)雜度為 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;
}

// 測(cè)試
const nums = [2,7,11,15];
console.log(twoSum(nums,26));
▉ 總結(jié)：
1、涉及到查找、判斷是否存在，相關(guān)的數(shù)據(jù)結(jié)構(gòu)有散列表、平衡二叉樹(shù)、二分查找、跳表、二叉查找樹(shù)。
2、使用數(shù)據(jù)結(jié)構(gòu)的時(shí)候注意適用條件。


3、注意對(duì)時(shí)間復(fù)雜度、空間復(fù)雜度的優(yōu)化策略。

歡迎一起加入到 LeetCode 開(kāi)源 Github 倉(cāng)庫(kù)，可以向 me 提交您其他語(yǔ)言的代碼。在倉(cāng)庫(kù)上堅(jiān)持和小伙伴們一起打卡，共同完善我們的開(kāi)源小倉(cāng)庫(kù)！
Github：https://github.com/luxiangqia...


歡迎關(guān)注我個(gè)人公眾號(hào)：「一個(gè)不甘平凡的碼農(nóng)」，記錄了自己一路自學(xué)編程的故事。

文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請(qǐng)注明本文地址：http://systransis.cn/yun/103162.html

相關(guān)文章

  • LeetCode 之 JavaScript 解答第二題 —— 兩數(shù)相加（Add Two Number

    摘要：多位數(shù)加多位數(shù)，反轉(zhuǎn)鏈表轉(zhuǎn)化整數(shù)，如果整數(shù)相加，可能會(huì)溢出，此方法行不通。直接進(jìn)行位數(shù)運(yùn)算，兩鏈表每取出一個(gè)就做運(yùn)算，將結(jié)果放入到新鏈表中。求和運(yùn)算會(huì)出現(xiàn)額外的進(jìn)位一般進(jìn)位與最高位進(jìn)位兩種情況。兩位數(shù)取模運(yùn)算。 Time：2019/4/2Title: ADD Two NumbersDifficulty: mediumAuthor:小鹿公眾號(hào)：一個(gè)不甘平凡的碼農(nóng)。 題目二：ADD Two...

    Sunxb 評(píng)論0 收藏0

  • 前端 | 每天一個(gè) LeetCode

    摘要：在線網(wǎng)站地址我的微信公眾號(hào)完整題目列表從年月日起，每天更新一題，順序從易到難，目前已更新個(gè)題。這是項(xiàng)目地址歡迎一起交流學(xué)習(xí)。 這篇文章記錄我練習(xí)的 LeetCode 題目，語(yǔ)言 JavaScript。 在線網(wǎng)站：https://cattle.w3fun.com GitHub 地址：https://github.com/swpuLeo/ca...我的微信公眾號(hào)： showImg(htt...

    張漢慶 評(píng)論0 收藏0

  • LeetCode - 001 - 兩數(shù)之和（two-sum）

    摘要：解法返回目錄解題代碼執(zhí)行測(cè)試解題思路使用雙重循環(huán)破解。解法返回目錄解題代碼執(zhí)行測(cè)試知識(shí)點(diǎn)遍歷數(shù)組，返回遍歷項(xiàng)，返回當(dāng)前索引。 Create by jsliang on 2019-05-16 22:19:13 Recently revised in 2019-05-17 14:22:40 Hello 小伙伴們，如果覺(jué)得本文還不錯(cuò)，記得給個(gè) star ， 小伙伴們的 star 是我持續(xù)更新的動(dòng)...

    habren 評(píng)論0 收藏0

  • [Leetcode] Two Sum 兩數(shù)和

    摘要：如果存在該差值，說(shuō)明存在兩個(gè)數(shù)之和是目標(biāo)和。而哈希表方法中的則可以換成。如果要求的不是兩個(gè)數(shù)和和，而是找兩個(gè)數(shù)之差為特定值的配對(duì)呢同樣用哈希表可以解決。 Two Sum Given an array of integers, find two numbers such that they add up to a specific target number.The function t...

    pkhope 評(píng)論0 收藏0

  • LeetCode 167：兩數(shù)之和 II - 輸入有序數(shù)組 Two Sum II - Input a

    摘要：公眾號(hào)愛(ài)寫(xiě)給定一個(gè)已按照升序排列的有序數(shù)組，找到兩個(gè)數(shù)使得它們相加之和等于目標(biāo)數(shù)。函數(shù)應(yīng)該返回這兩個(gè)下標(biāo)值和，其中必須小于。示例輸入輸出解釋與之和等于目標(biāo)數(shù)。 公眾號(hào)： 愛(ài)寫(xiě)bug（ID：icodebugs） 給定一個(gè)已按照升序排列 的有序數(shù)組，找到兩個(gè)數(shù)使得它們相加之和等于目標(biāo)數(shù)。 函數(shù)應(yīng)該返回這兩個(gè)下標(biāo)值 index1 和 index2，其中 index1 必須小于 index2。...

    張春雷 評(píng)論0 收藏0

發(fā)表評(píng)論

0條評(píng)論

最新活動(dòng)
閱讀需要支付1元查看
<