Go 刷 leetcode｜經(jīng)典力扣第一題

今天為大家講解 LeetCode 第 1 題，是一道簡單但相當(dāng)經(jīng)典的題目。

題目描述

給定一個(gè)整數(shù)數(shù)組 nums 和一個(gè)目標(biāo)值 target，請你在該數(shù)組中找出和為目標(biāo)值的那 兩個(gè) 整數(shù)，并返回他們的數(shù)組下標(biāo)。

你可以假設(shè)每種輸入只會對應(yīng)一個(gè)答案。但是，數(shù)組中同一個(gè)元素不能使用兩遍。

示例:

給定 nums = [2, 7, 11, 15], target = 9

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

來源：力扣（LeetCode） 鏈接：https://leetcode-cn.com/problems/two-sum 著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有。商業(yè)轉(zhuǎn)載請聯(lián)系官方授權(quán)，非商業(yè)轉(zhuǎn)載請注明出處。

解題思路

暴力法

遍歷每個(gè)元素 x，并查找是否存在一個(gè)值與 target - x 相等的目標(biāo)元素。

//go
func?twoSum(nums?[]int,?target?int)?[]int?{
????length?:=?len(nums)
????ans?:=?make([]int,0)
????for?i?:=?0;?i????????for?j?:=?i+1;?j????????????if?nums[i]?+?nums[j]?==?target{
????????????????ans?=?append(ans,?i,?j)
????????????}
????????}
????}
????return?ans
}

//java
class?Solution?{
????public?int[]?twoSum(int[]?nums,?int?target)?{
????????for?(int?i?=?0;?i?????????????for?(int?j?=?i?+?1;?j?????????????????if?(nums[j]?==?target?-?nums[i])?{
????????????????????return?new?int[]?{?i,?j?};
????????????????}
????????????}
????????}
????????throw?new?IllegalArgumentException("No?two?sum?solution");
????}
}

復(fù)雜度分析：

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

哈希表法

通過以空間換取速度的方式，我們可以將查找時(shí)間從 O(n) 降低到 O(1)。哈希表正是為此目的而構(gòu)建的，它支持以近似恒定的時(shí)間進(jìn)行快速查找。

我們可以將每個(gè)元素的值和它的索引添加到哈希表中，然后在遍歷時(shí)檢查每個(gè)元素對應(yīng)的目標(biāo)元素（target - nums[i]）是否存在于表中。注意??，該目標(biāo)元素不能是 nums[i] 本身！

//go
func?twoSum(nums?[]int,?target?int)?[]int?{
????result?:=?make([]int,?0)
????m?:=?make(map[int]int,?length)
????for?i,k?:=?range?nums{
??//?判斷map中是否存在key為[target?-?k]的值
??if?value,exist?:=?m[target?-?k];exist?&&?value?!=?i{
???// append：尾部追加元素
???result?=?append(result,value)
???result?=?append(result,?i)
??}
??m[k]?=?i
?}
?return?result
}

//java
class?Solution?{
????public?int[]?twoSum(int[]?nums,?int?target)?{
????????Map?map?=?new?HashMap<>();
????????for?(int?i?=?0;?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");
????}
}

鄭重聲明：

所展示代碼已通過 LeetCode 運(yùn)行通過，請放心食用～