小編給大家分享一下LeetCode如何實(shí)現(xiàn)兩數(shù)之和，相信大部分人都還不怎么了解，因此分享這篇文章給大家參考一下，希望大家閱讀完這篇文章后大有收獲，下面讓我們一起去了解一下吧！

創(chuàng)新互聯(lián)公司專注于企業(yè)成都全網(wǎng)營(yíng)銷推廣、網(wǎng)站重做改版、河曲網(wǎng)站定制設(shè)計(jì)、自適應(yīng)品牌網(wǎng)站建設(shè)、H5建站、購(gòu)物商城網(wǎng)站建設(shè)、集團(tuán)公司官網(wǎng)建設(shè)、外貿(mào)營(yíng)銷網(wǎng)站建設(shè)、高端網(wǎng)站制作、響應(yīng)式網(wǎng)頁(yè)設(shè)計(jì)等建站業(yè)務(wù)，價(jià)格優(yōu)惠性價(jià)比高，為河曲等各大城市提供網(wǎng)站開(kāi)發(fā)制作服務(wù)。

題目：

給定一個(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ù)組中同樣的元素。

示例：

給定 nums = [2, 7, 11, 15], target = 9
因?yàn)?nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]

這是兩數(shù)之和的問(wèn)題，看似很簡(jiǎn)單，讀者可以先思考下如何實(shí)現(xiàn)。本文介紹三種實(shí)現(xiàn)方式，并且分析復(fù)雜度。

1. 暴力法

暴力法很簡(jiǎn)單。遍歷每個(gè)元素 xx，并查找是否存在一個(gè)值與 target - xtarget?x 相等的目標(biāo)元素。代碼示例如下：

public int[] twoSum(int[] nums, int target) {
       int[] result = new int[2];
       for(int i = 0; i < nums.length; i++) {
           for(int j = i + 1; j < nums.length; j++) {
               if(nums[i] + nums[j] == target) {
                   result[0] = i;
                   result[1] = j;
                   return result;
               }
           }
       }
       return result;
}

算法復(fù)雜度分析：

時(shí)間復(fù)雜度：O(n^2)， 對(duì)于每個(gè)元素，我們?cè)噲D通過(guò)遍歷數(shù)組的其余部分來(lái)尋找它所對(duì)應(yīng)的目標(biāo)元素，這將耗費(fèi) O(n) 的時(shí)間。因此時(shí)間復(fù)雜度為 O(n^2)。

空間復(fù)雜度：O(1)。

2. 兩遍哈希表

為了對(duì)運(yùn)行時(shí)間復(fù)雜度進(jìn)行優(yōu)化，我們需要一種更有效的方法來(lái)檢查數(shù)組中是否存在目標(biāo)元素。如果存在，我們需要找出它的索引。保持?jǐn)?shù)組中的每個(gè)元素與其索引相互對(duì)應(yīng)的最好方法是什么？哈希表。

通過(guò)以空間換取速度的方式，我們可以將查找時(shí)間從 O(n) 降低到 O(1)。哈希表正是為此目的而構(gòu)建的，它支持以 近似 恒定的時(shí)間進(jìn)行快速查找。我用“近似”來(lái)描述，是因?yàn)橐坏┏霈F(xiàn)沖突，查找用時(shí)可能會(huì)退化到 O(n)。但只要你仔細(xì)地挑選哈希函數(shù)，在哈希表中進(jìn)行查找的用時(shí)應(yīng)當(dāng)被攤銷為 O(1)。

一個(gè)簡(jiǎn)單的實(shí)現(xiàn)使用了兩次迭代。在第一次迭代中，我們將每個(gè)元素的值和它的索引添加到表中。然后，在第二次迭代中，我們將檢查每個(gè)元素所對(duì)應(yīng)的目標(biāo)元素（target - nums[i]）是否存在于表中。注意，該目標(biāo)元素不能是 nums[i] 本身！

public int[] twoSum(int[] nums, int target) {
   Map<Integer, Integer> map = new HashMap<>();
   for (int i = 0; i < nums.length; i++) {
       map.put(nums[i], i);
   }
   for (int i = 0; i < nums.length; i++) {
       int complement = target - nums[i];
       if (map.containsKey(complement) && map.get(complement) != i) {
           return new int[] { i, map.get(complement) };
       }
   }
   throw new IllegalArgumentException("No two sum solution");
}

復(fù)雜度分析：

時(shí)間復(fù)雜度：O(n)， 我們把包含有 n 個(gè)元素的列表遍歷兩次。由于哈希表將查找時(shí)間縮短到 O(1) ，所以時(shí)間復(fù)雜度為 O(n)。

空間復(fù)雜度：O(n)， 所需的額外空間取決于哈希表中存儲(chǔ)的元素?cái)?shù)量，該表中存儲(chǔ)了 n  個(gè)元素。

3. 一遍哈希表

事實(shí)證明，我們可以一次完成。在進(jìn)行迭代并將元素插入到表中的同時(shí)，我們還會(huì)回過(guò)頭來(lái)檢查表中是否已經(jīng)存在當(dāng)前元素所對(duì)應(yīng)的目標(biāo)元素。如果它存在，那我們已經(jīng)找到了對(duì)應(yīng)解，并立即將其返回。

public int[] twoSum(int[] nums, int target) {
   Map<Integer, Integer> map = new HashMap<>();
   for (int i = 0; i < nums.length; i++) {
       int complement = target - nums[i];
       if (map.containsKey(complement)) {
           return new int[] { map.get(complement), i };
       }
       map.put(nums[i], i);
   }
   throw new IllegalArgumentException("No two sum solution");
}

復(fù)雜度分析：

時(shí)間復(fù)雜度：O(n)， 我們只遍歷了包含有 nn 個(gè)元素的列表一次。在表中進(jìn)行的每次查找只花費(fèi) O(1) 的時(shí)間。

空間復(fù)雜度：O(n)， 所需的額外空間取決于哈希表中存儲(chǔ)的元素?cái)?shù)量，該表最多需要存儲(chǔ) n 個(gè)元素。

以上是“LeetCode如何實(shí)現(xiàn)兩數(shù)之和”這篇文章的所有內(nèi)容，感謝各位的閱讀！相信大家都有了一定的了解，希望分享的內(nèi)容對(duì)大家有所幫助，如果還想學(xué)習(xí)更多知識(shí)，歡迎關(guān)注創(chuàng)新互聯(lián)-成都網(wǎng)站建設(shè)公司行業(yè)資訊頻道！

名稱欄目：LeetCode如何實(shí)現(xiàn)兩數(shù)之和-創(chuàng)新互聯(lián)
本文地址：http://www.rwnh.cn/article18/dosigp.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供微信小程序、小程序開(kāi)發(fā)、網(wǎng)站建設(shè)、自適應(yīng)網(wǎng)站、網(wǎng)站制作、響應(yīng)式網(wǎng)站

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請(qǐng)盡快告知，我們將會(huì)在第一時(shí)間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng)，如需處理請(qǐng)聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時(shí)需注明來(lái)源： 創(chuàng)新互聯(lián)