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)));
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

思路二：

“逆向”解题思路

为什么叫“逆向”呢？这个词的出发点是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)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

思路三：

测试结果：

测试效率：

代码：

1