LeetCode Top100:两数之和-java版

题目在这里插入图片描述

解题思路 思路一：双for循环

直系思维：两个for循环查找数据，能够很直观的解出来，但响应时间很长，属于低效率代码。 我一开始做这道题用的就是这个方法哈哈

测试结果： 测试效率： 时间复杂度为：O(n^2)

代码：

public class 两数之和 { public static int[] twoSum(int[] nums, int target) { for (int i = 0; i < nums.length-1; i++) { for (int j = i+1; j < nums.length; j++) { if(nums[i]+nums[j]==target){ //同一个元素不能重复出现 if(i==j){ continue; } return new int[] {i,j}; } } } return new int[]{}; } public static void main(String[] args) { int[] nums=new int[]{2,7,11,15}; int target=9; System.out.println(Arrays.toString(twoSum(nums,target))); } } 

思路二：

“逆向”解题思路

为什么叫“逆向”呢？这个词的出发点是Map的用途。

• 在我们一般的“正向”解题思路中，我们坑定要想在Map初始化过程中先把所有数据都存储，然后作为判断“元素是否存在”的依据。

• 而在“逆向”解题思路中，Map在初始化过程中什么元素都不放，而当待匹配的元素不存在Map中的时候，才把它放入的Map中。具体步骤如下所示：

步骤一：初始化一个空的Map，其中key存储数组里的值，value存储的是数组的下标index。指向的值为2，待匹配的值为12，而12并没有在Map中，所以将2放入到Map中。如下所示：

步骤二：i指向的值为7，待匹配的值为7，而7并没有在Map中，所以将7放入到Map中。如下所示：

步骤三：i指向的值为11，待匹配的值为3，而3并没有在Map中，所以将3放入到Map中。如下所示：

步骤四：i指向的值为7，待匹配的值为7，而7存在于Map中，所以匹配成功，返回结果：result=[3, 1]。如下所示：

【总结】

这种“逆向”解题思路只需要一次循环就可以了，并且Map数组不用提前初始化，在性能和内存占用率都很低

参考文档1

测试结果：

测试效率： 时间复杂度为：O(n^2)

时间复杂度

代码：

public class 两数之和2 { public static int[] twoSum(int[] nums, int target) { //key:存储值 value存储下标 HashMap<Integer, Integer> map = new HashMap<>(); for (int i = 0; i < nums.length; i++) { Integer index; index=target-nums[i]; //如果map中找得到 if(map.get(index)!=null){ return new int[] {map.get(index),i}; }else{ //如果map中找不到，就放进map map.put(nums[i],i); } } return new int[]{}; } public static void main(String[] args) { int[] nums=new int[]{2,7,11,15}; int target=9; System.out.println(Arrays.toString(twoSum(nums,target))); } }![在这里插入图片描述](https://img-blog.csdnimg.cn/67de640eccdd434f80abdc3ee19f19be.png) 

思路三：

测试结果：

测试效率：

代码：