【LeetCode100】--- 1.两数之和【复习回滚】

题目传送门

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

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 个数全部添加进来