給定一個整數(shù)數(shù)組 nums 和一個整數(shù)目標(biāo)值 target，請你在該數(shù)組中找出 和為目標(biāo)值 target 的那 兩個 整數(shù)，并返回它們的數(shù)組下標(biāo)。你可以假設(shè)每種輸入只會對應(yīng)一個答案。但是，數(shù)組中同一個元素在答案里不能重復(fù)出現(xiàn)。你可以按任意順序返回答案。

首先該題要求時間復(fù)雜度低于O(n^2)，可以采用空間換時間的方法采用哈希表的方式。
key為target與num[]中值之差，value為num[]中值的下標(biāo)。檢查哈希表中是否存在target與當(dāng)前值之差：如果存在則返回該結(jié)果，如果不存在則將其存入哈希表中。

public int[] twoSum(int[] nums, int target) {Map<Integer,Integer> map = new HashMap<>();for(int i = 0; i < nums.length; i++){if(map.containsKey(target - nums[i])) {return new int[] {map.get(target - nums[i]), i};}map.put(nums[i], i);}//throw new IllegalArgumentException("No two sum solution");//題解中還有拋出異常的做法，但是不了解兩者優(yōu)劣，希望有大神不吝賜教return new int[0];} }

使用哈希表的方法很簡單易懂，需要注意的就是哈希沖突的問題，上述方法可以有效避開hash沖突。每次寫入時，判斷條件不是當(dāng)前的key本身存不存在，而是key和tag之間的差值存不存在，這一點(diǎn)很重要。假定只有一個解，也就是說重復(fù)元素再多都無所謂。如果有3個或者以上的重復(fù)元素，代表這個重復(fù)元素不可能是解，所以寫入map的時候直接覆蓋也無所謂；如果只有兩個重復(fù)元素，同樣的道理，假如這個重復(fù)元素是解，那么必定是兩個重復(fù)元素的和等于tag。這種情況下，當(dāng)遇到第二個重復(fù)元素時，不會寫入map，這個時候直接已經(jīng)取到解了。 所以這種方式，不用考慮hash沖突的問題。

總結(jié)

以上是生活随笔為你收集整理的1. 两数之和（Java）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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