hot100 1.两数之和

一、方法一：暴力。

1.思路：先枚举下标i，再枚举下标j，然后判断nums[i] + nums[j] == target。

2.复杂度分析：

（1）时间复杂度：O(n^2)，两层for循环，其中n为nums的长度。

（2）空间复杂度：O(1)，仅用到了若干额外变量。

附代码：

class Solution { public int[] twoSum(int[] nums, int target) { for(int i = 0;;i++){ //枚举i，因为题目保证有解，所以可不加遍历条件，并用无限循环省略最后的return语句 //如果加了i < nums.length，编译器反而会在编译时做静态代码分析时认为循环结束时可能没有返回值，会报错error: missing return statement for(int j = i + 1;j < nums.length;j++){ //枚举i右边的j if(nums[i] + nums[j] == target){ return new int[] {i,j}; //返回下标 } } } } }

二、方法二：哈希表

1.思路：如下图所示。

2.复杂度分析：

（1）时间复杂度：O(n)，其中n为nums的长度。

（2）空间复杂度：O(n)，哈希表需要O(n)的空间。

附代码：

class Solution { public int[] twoSum(int[] nums, int target) { Map<Integer,Integer> map = new HashMap<>(); for(int j = 0;;j++){//枚举j int x = nums[j]; //在左边找满足target - nums[j]的nums[i] if(map.containsKey(target - x)){ //找到了 return new int[]{map.get(target - x),j}; //返回两个数的下标 } map.put(x,j); //还没找到，先保存当前nums[j]和j至哈希表 } } }