LeetCode-两数之和 java思路

for循环嵌套法

正常人思路肯定是两层for循环嵌套，这种方法简单粗暴，不说了，上才艺：

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

（最终用时 122ms  内存消耗37.9M  执行用时已经战胜 5.01 % 的 java 提交记录）

接下来我们考虑如何优化，开始考虑了直接进行大小比较再for循环，比如要找的是5如果这个数比5大就不循环里面一层，但是报错了。测试数据有负数。

这种找值很容易想到查找次数接近于1的hashMap，接下来使用hashMap进行优化：

HashMap用key找值方法

两次循环，key存数字，value储存数组索引。看起来很完美，然而执行用时只超过74%的java用户，肯定是还有其他方法呀！

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

（执行用时：3 ms   内存消耗：40.2 MB   执行用时已经战胜 74.03 % 的 java 提交记录）

 

HashMap优化

我们可以看到填充数据过程漫长而且浪费！既然查询速度接近于1我们不如每一次添加就找找看~~

但是我们不知道会不会有重复的元素存在，为了避免一样的key把value覆盖，我们最好是先拿这个值去找有没有能和自己相加为target的数，之后再添加。

（貌似不大好理解，这里也是提交后错了我才发现的，测试数据 3，3   希望求和：6 如果我们先添加在查找会出错，因为这个3,1 已经把 3,0 覆盖掉了，所以得不到答案。而且注意，为了小的数在前面，这次返回的两个数字顺序和之前不一样 ）

正确解法：

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

            map.put(nums[i], i);
        }
        return null;
    }
}

（执行用时：2 ms   内存消耗：39.9 MB   执行用时已经战胜 99.61 % 的 java 提交记录）

想不到剩下0.39%用户怎么做的了，欢迎大佬补充