LeetCode題庫整理【Java】

1.兩數之和

題目：給定一個整數數組和一個目標值，找出數組中和為目標值的兩個數。你可以假設每個輸入只對應一種答案，且同樣的元素不能被重復利用。
示例:

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

方法一：這道題目比較容易想到的是通過暴力搜索求解，但暴力搜索的時間復雜度為 O(n^2)。Java代碼如下：

public class SumOfTwoNums {public static void main(String[] args) {int[] nums=new int[] {-3,4,3,90};int target=0;SumOfTwoNums solution=new SumOfTwoNums();solution.twoSum(nums, target);}public int[] twoSum(int[] nums, int target) { int index[]=new int[]{0,0};for(int i=0;i<nums.length-1;i++) {for(int j=i+1;j<nums.length;j++) {if( (target-nums[i]==nums[j]) ) {index[0]=i;index[1]=j;System.out.println(index[0]+" "+index[1]);break;}} }return index;} }

在LeetCode中提交的結果如下：

方法二：使用哈希的思想，利用Python中list的查詢方式，我們可以將復雜度降低到 O(n)。有兩個值得注意的地方：
（1）. 同樣的元素不能重復使用（也就是不能自己加自己） （2）. 給定的數組中可能有相同的元素（比如 [3, 3, 4, 4, 5]），也可能會有負數（比如[-3,0,3,8,10]）

HashMap是Java中集合的一部分。它提供了Java的Map接口的基本實現。它將數據存儲在（Key，Value）對中。

void clear()：用于從Map中刪除所有映射。
boolean containsKey(Object key)：用于如果對于指定的鍵，映射value存在于映射中則返回True。
boolean containsValue(Object value)：用于在一個或多個鍵映射到指定值時返回true。
boolean isEmpty()：用于檢查映射是否為空。如果地圖為空，則返回true。
set entrySet()：用于返回哈希映射的set視圖。
Object get(Object key)：用于檢索或獲取特定鍵映射的值。
Set keySet()：用于返回鍵的設置視圖。
int size()：用于返回Map的大小。
Object put(Object key，Object value)：用于將鍵值對的特定映射插入到映射中。
putAll(Map M)：用于將所有元素從一個Map復制到另一個Map。
Object remove(Object key)：用于刪除Map中任何特定鍵的值。

class Solution {public int[] twoSum(int[] nums, int target) {HashMap<Integer,Integer> hm=new HashMap<Integer,Integer>();int res[]=new int[2];for(int i=0;i<nums.length;i++) {if( hm.containsKey(target-nums[i]) ) {//hm.put(nums[i], i);//此行前置就可能出現自己加自己的情況，比如nums={3,2，4}，target=6，運行結果為[0,0]; 實際應該為[1,2]res[0]=i;res[1]=hm.get(target-nums[i]);System.out.println(res[0]+" "+res[1]);break;}hm.put(nums[i], i);//此行不能前置}return res;} }

對比可以看見運行時間縮短了很多。

總結

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

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