兩數之和

LeetCode題庫第1題 兩數之和

看到題，我就想到了暴力法：

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

時間復雜度為n2,空間復雜度為1，沒想到過了！

??通過兩個for循環來得到兩個數的下標，在第二個for循環時要注意，因為i之前的數都匹配過了。你可以看下圖：

另外，題目說，你可以假設每種輸入都只有一種答案，所以，只要找到索引i所對應的值和索引j對應的值相加等于target，就可以將i和j作為數組的兩個元素并將數組輸出。代碼的最后一句在本題中永遠也不會執行，但是也不能刪除，刪除后會報錯，因為兩個for循環之外沒有返回。

??另外，看了官方題解，還有一種用哈希表的解法，很巧妙。先構造一個哈希表，其中的鍵是數組中的值，值是數組下標，依次遍歷數組，

• 當哈希表中的鍵（就是數組中的值）包含（target-nums[i])，找到的兩個索引就是當前的i和哈希表中鍵為（target-nums[i]）所對應的值。

• 當哈希表中的鍵（就是數組中的值）不包含（target-nums[i]), 就將當前數組中下標i所對應的值作為鍵，i作為值，將它們加入到哈希表中。

public int[] useHashMap(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[] {};}

總結

以上是生活随笔為你收集整理的LeetCode题库第1题 两数之和的全部內容，希望文章能夠幫你解決所遇到的問題。

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