算法「两数之和-哈希」

利用HashMap 减少查询时间

在暴力法中，内层循环查找差值很浪费时间，那么如何减少查询时间呢？利用HashMap 就可以减少查询时间。使用一层循环，每遍历到一个元素就计算该元素与 target 之间的差值，然后HashMap 中寻找该差值，如果找到，则返回两个元素在数组nums 的下标，如果没有找到，则将当前元素存入HashMap中

class Solution {

    public int[] twoSum(int[] nums, int target) {

        HashMap<Integer,Integer> map = new HashMap<>();

        int[] Opt = new int[2];

        for (int i = 0; i < nums.length; i++) {

            int dif = target - nums[i];

            if (map.get(dif) != null) {

                Opt[0] = map.get(dif);

                Opt[1] = i;

                return Opt;

            }

            map.put(nums[i],i);

        }

        return Opt;

    }

}

//调用hashmap函数，containsKey方法

class Solution {

    public int[] twoSum(int[] nums, int target) {

        Map<Integer, Integer> map = new HashMap<>();

        for (int i = 0; i < nums.length; i++) {

            map.put(nums[i], i);

        }

        for (int i = 0; i < nums.length; i++) {

            int complement = target - nums[i];

            if (map.containsKey(complement) && map.get(complement) != i) {

                return new int[] { i, map.get(complement) };

            }

        }

        throw new IllegalArgumentException("No two sum solution");

    }

}

时间复杂度：

O(n)。