文章目錄

• 一. 題目描述
• 二. 解法
• • • ① 暴力破解
    • ② 靜態(tài)哈希表
    • • • 1. 為什么用哈希表來(lái)做
        • 2. 特殊情況：兩數(shù)相同，map映射覆蓋
    • ③ 動(dòng)態(tài)哈希表
    • ④ 未解之謎

誒嘿，經(jīng)典開(kāi)頭題目

一. 題目描述

數(shù)組中同一個(gè)元素不能使用兩遍：

• 見(jiàn)實(shí)例2，實(shí)際過(guò)程可能出現(xiàn)輸出為[0,0]的情況，就是同一元素使用了兩遍，要注意判斷

二. 解法

① 暴力破解

看到題干，首選暴力。
只需要遍歷數(shù)組：對(duì)于數(shù)組中的每一個(gè)元素，都和后面的所有元素進(jìn)行一次匹配即可。

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

• 時(shí)間復(fù)雜度為O($n^2$)，空間復(fù)雜度為O(1)

現(xiàn)在題目解出來(lái)了，但是要怎么優(yōu)化呢？
看到上述的時(shí)空復(fù)雜度，可以這么想：時(shí)間復(fù)雜度和空間復(fù)雜度不太均衡，可不可以試一下把時(shí)間上的負(fù)擔(dān)分一點(diǎn)到空間上呢？

② 靜態(tài)哈希表

class Solution {public int[] twoSum(int[] nums, int target) {Map<Integer, Integer> hashtable = new HashMap<Integer, Integer>();// 先構(gòu)建哈希表for(int i=0;i<nums.length; ++i)hashtable.put(nums[i],i);// 再遍歷數(shù)組，結(jié)合哈希表進(jìn)行查找for(int i=0;i<nums.length; ++i){if(hashtable.containsKey(target - nums[i])){// 這邊這個(gè)判斷不能少，否則出現(xiàn)同一元素使用兩次的情況if(hashtable.get(target - nums[i])!=i)return new int[]{hashtable.get(target - nums[i]),i};}}return new int[0];} }

• 時(shí)間復(fù)雜度O(n)，空間復(fù)雜度O(n)

1. 為什么用哈希表來(lái)做

暴力法的時(shí)間復(fù)雜度由來(lái)：n(遍歷數(shù)組元素）* n(查找能和當(dāng)前數(shù)組組合成target的元素）。
而這個(gè)查找的O(n)，如果是用哈希表來(lái)實(shí)現(xiàn)則是O(1)。
而由于需要構(gòu)建出哈希表，我們需要付出O(n)的空間復(fù)雜度代價(jià)。

2. 特殊情況：兩數(shù)相同，map映射覆蓋

描述：使用兩個(gè)數(shù)據(jù)值相同，下標(biāo)不同的元素。而我們?cè)诮⒂成浔頃r(shí)使用的鍵值是數(shù)據(jù)值，因此下標(biāo)大的元素會(huì)覆蓋之前的元素，變成新的映射，導(dǎo)致有些映射會(huì)丟失。

理解：考慮了好久。。。其實(shí)這樣子不會(huì)出問(wèn)題。

• 首先保留的是下標(biāo)大的元素的映射
• 然后，我們?cè)诒闅v時(shí)使用的是數(shù)組，而且是先遇到下標(biāo)小的元素。
  對(duì)這個(gè)小的元素進(jìn)行哈希表查找，剛好可以找到下標(biāo)大的元素。就可以得到正確的結(jié)果

③ 動(dòng)態(tài)哈希表

class Solution {public int[] twoSum(int[] nums, int target) {Map<Integer, Integer> hashtable = new HashMap<Integer, Integer>();for (int i = 0; i < nums.length; ++i) {if (hashtable.containsKey(target - nums[i])) {return new int[]{hashtable.get(target - nums[i]), i};}hashtable.put(nums[i], i);}return new int[0];} }

• 時(shí)間復(fù)雜度O(n)，空間復(fù)雜度O(n)
• 目前了解的最好的方法
• 在②的基礎(chǔ)上，會(huì)比較好理解
• 在②之上的優(yōu)化：

不需要進(jìn)行相同元素的判斷：當(dāng)出現(xiàn)與之前值相同，并且可以組成target的值時(shí)，就直接滿足return條件了。
比如實(shí)例3，先存儲(chǔ)<3，0>映射；到nums[1]的時(shí)候，不需要覆蓋<3，1>映射，而是滿足if判斷，直接返回[0，1]。

占用的時(shí)間空間會(huì)更小：因?yàn)槭且贿吔ü１硪贿呎襛nswer的，所以很大概率在完全建表之前就找到answer。

④ 未解之謎

這一塊是無(wú)傷大雅，但是想弄明白的地方

增強(qiáng)型for循環(huán)溢出
= =這個(gè)解決了，應(yīng)該把nums改成nums.length，還是用得不夠熟悉。

// 正常for循環(huán)，不會(huì)出錯(cuò) for(int i=0;i<nums.length; ++i)hashtable.put(nums[i],i); // 增強(qiáng)型for循環(huán)，會(huì)出現(xiàn)越界錯(cuò)誤 for(int i : nums)hashtable.put(nums[i],i);

需要額外寫(xiě)return

// ②③如果只有if的return，編譯器會(huì)報(bào)錯(cuò)：“missing return statement”，但是①卻不需要 return new int[0];

總結(jié)

以上是生活随笔為你收集整理的【LeetCode笔记】1. 两数之和（JAVA、哈希表）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。