文章目錄

• Q
• A - 1 暴力破解
• Q -2 查找表法

---

Q

給定一個整數數組 nums 和一個目標值 target，請你在該數組中找出和為目標值的那 兩個 整數，并返回他們的數組下標。

你可以假設每種輸入只會對應一個答案。但是，數組中同一個元素不能使用兩遍。

示例:

給定 nums = [2, 7, 11, 15], target = 9因為 nums[0] + nums[1] = 2 + 7 = 9 所以返回 [0, 1]

---

A - 1 暴力破解

枚舉數組中的每一個數 x，尋找數組中是否存在 target - x

使用遍歷整個數組的方式尋找 target - x 時，需要注意到每一個位于 x 之前的元素都已經和 x 匹配過，因此不需要再進行匹配。

而每一個元素不能被使用兩次，所以我們只需要在 x 后面的元素中尋找 target - x。

public class TwoSum {public static int[] twoSum(int[] nums, int target) {int len = nums.length ;for (int i = 0; i < len; i++) {for (int j = i+1 ; j < len ; j++){if (nums[i] + nums[j] == target){return new int[]{i,j};}}}return new int[0];}public static void main(String[] args) {int[] nums = new int[]{1,3,4,2};int target = 6;int[] targetArr = twoSum(nums, target);System.out.println(targetArr[0]);System.out.println(targetArr[1]);} }

復雜度分析

時間復雜度：O(N^2)，其中 N 是數組中的元素數量。最壞情況下數組中任意兩個數都要被匹配一次。

空間復雜度：O(1) ,只用到了常數個變量

---

Q -2 查找表法

上面暴力破解的方法我們也看到了，時間復雜度 O(N^2) ， 如何優化呢？

通常都是使用 空間換時間

比如我們在遍歷的同時，去記錄一些信息，為了是去掉一層循環。 那如果要記錄已經遍歷的數值和它對應的下標， 可以借助查找表發來實現。

常用的查找表的兩個實現是

哈希表

平衡二叉搜索樹

因為這里沒有排序的需求，所以使用哈希表即可。

public static int[] twoSum2(int[] nums, int target) {int len = nums.length;Map<Integer, Integer> map = new HashMap<Integer, Integer>(len - 1);for (int i = 0; i < len; i++) {int another = target - nums[i] ;if (map.containsKey(another)){return new int[]{map.get(another),i};}map.put(nums[i], i);}return new int[0];}

遍歷數組 nums，i 為當前下標，每個值都判斷map中是否存在 target-nums[i] 的 key 值；
如果存在則找到了兩個值，如果不存在則將當前的 (nums[i],i) 存入 map 中，繼續遍歷直到找到為止

復雜度分析

時間復雜度：O(N)，其中 NN 是數組中的元素數量。對于每一個元素 x，我們可以 O(1)地尋找 target - x。

空間復雜度：O(N)，其中 NN 是數組中的元素數量。主要為哈希表的開銷。

---

總結

以上是生活随笔為你收集整理的leetcode - two-sum的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。