題目傳送門

解法一：暴力枚舉（也是最容易想到的）?

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

注意 初始化 j
int j = i+1
因為j和i不能重復。?

復雜度分析：

時間復雜度：O（N2） 雙重循環
空間復雜度：O（1）代碼只使用了幾個變量 i 、j、n。

解法二：哈希表 （HashMap）
?

class Solution {public int[] twoSum(int[] nums, int target) {Map<Integer,Integer> map = new HashMap<>();int n = nums.length;for(int i = 0; i<n; i++){int x = target-nums[i];if(map.containsKey(x)){return new int[]{map.get(x),i};}map.put(nums[i],i);}return new int[]{-1,-1};}
}

哈希表中
key：記錄數組中的數
value：記錄數組下標
直接在哈希表中查找? map.containsKey(x)
x = targer-num[ i ]? ?
若找到了說明此時? x+num[i] = target 就

找到答案了
返回數組 new int[]{map.get(x),i}
因為此時 i 一定是兩個數中靠數組后面的那個數的數組下標
而map.get(x) 就是數組中兩數靠前的數組下標

如果沒找到就 map.put(nums[i],i);
題目說了會有一組答案的，因此繼續在哈希表中找 x = targer-num[ i ] 總會找到答案。

繼續循環

復雜度分析

時間復雜度：O（n）一次for循環，最多循環n次。而哈希表查找每次只需要常量次。
空間復雜度：O（n）建立了哈希表，最快情況 數組中 n-1 個數全部添加進來