文章目錄

• • LeetCode 1. Two Sum (兩數(shù)之和）
  • • • 題目描述
      • 樣例
      • 解題思路一(暴力法)
      • 解題思路二(使用map)

前言：最近業(yè)余時(shí)間，一直在看LeetCode上面的題，上面有許多好的解題思路可以借鑒到我們真正的項(xiàng)目中。總之，要靜下心來(lái)認(rèn)真研究，對(duì)我們無(wú)論是目前做的項(xiàng)目還是以后出去面試，都會(huì)有很大的幫助。

LeetCode 1. Two Sum (兩數(shù)之和）

題目描述

給定一個(gè)整型數(shù)組，要求返回兩個(gè)數(shù)的下標(biāo)，使得兩數(shù)之和等于給定的目標(biāo)值，要求同一個(gè)下標(biāo)不能使用兩次。
數(shù)據(jù)保證有且僅有一組解。

樣例

給定數(shù)組 nums = [2, 7, 11, 15]，以及目標(biāo)值 target = 9，

由于 nums[0] + nums[1] = 2 + 7 = 9,
所以 return [0, 1].

解題思路一(暴力法)

這個(gè)我們大家只要寫(xiě)過(guò)一兩年代碼都會(huì)想到，就是兩遍for循環(huán)就可以搞定。

核心代碼如下：

//暴力方法public static int[] twosum(int[] nums,int target) {for (int i = 0;i<nums.length;i++) {for (int j = i+1;j < nums.length;j++) {if (nums[j] == target - nums[i]) {return new int[] {j,i};}}}throw new IllegalArgumentException("No two sum solution");}

結(jié)果分析：

暴力枚舉方法很簡(jiǎn)單：兩重循環(huán)枚舉下標(biāo) i,j，然后判斷nums[i]+nums[j]nums[i]+nums[j] 是否等于 targettarget。時(shí)間復(fù)雜度：由于有兩重循環(huán)，所以復(fù)雜度是 O(n²)。

解題思路二(使用map)

• 遍歷數(shù)組 nums，i 為當(dāng)前下標(biāo)，每個(gè)值都判斷map中是否存在 target-nums[i] 的 key 值
• 如果存在則找到了兩個(gè)值，如果不存在則將當(dāng)前的 (nums[i],i) 存入 map 中，繼續(xù)遍歷直到找到為止
• 如果最終都沒(méi)有結(jié)果則拋出異常

核心代碼如下：

//哈希表public static int[] twosumMap(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");}

使用map時(shí)候可能大家會(huì)有疑問(wèn)，如果遇到{2,2}這樣數(shù)據(jù)會(huì)出現(xiàn)問(wèn)題，這一點(diǎn)我們做個(gè)小實(shí)驗(yàn)就可以看出是否有問(wèn)題。

public static void main(String[] args) {int[] nums = { 7,2,4, 11,2, 15};int[] twosum = twosumMap(nums, 4);System.out.println(Arrays.toString(twosum));}

結(jié)果為：[1, 4]

通過(guò)以上結(jié)果看出，如果出現(xiàn)重復(fù)的數(shù)據(jù)不會(huì)出現(xiàn)問(wèn)題。
個(gè)人公眾號(hào)：
微信粉絲群

總結(jié)

以上是生活随笔為你收集整理的LeetCode刷题-两数之和(持续更新)的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

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