leetcode1---Two Sum

Given an array of integers, return indices of the two numbers such that they add up to a specific target.

You may assume that each input would have exactly one solution, and you may not use the same element twice.

Example:

Given nums = [2, 7, 11, 15],

target = 9,Because nums[0] + nums[1] = 2 + 7 = 9,

return [0,1].

题目分析：要求求出一个数组中两个元素和为一个定值的问题，我们的第一想法自然是循环遍历两次，依次记录两个位置的值，这样自然是可以解的，但是这种解的时间复杂度为O(n^2),不过试了一下，这种解法也能过，代码就不上了。我们来分析能否降低算法复杂度，将其降到O(n)级别，我们如果想一次扫描就能得到正确结果的话，自然需要一个数据结构来记录之前扫描过的数据，然后判断这两个值的和是否为target，这里我们自然而然的可以想到用Map数据结构来存储已经遍历过的值和它的位置，PS：HashMap的查询效率是O(1)而不是O(n)，如果对于这个不了解的话可以去看一下hashMap的底层实现，当我们遍历到当前值nums[i]的时候，来查询map是否还有target-nums[i]这个键，如果有的话，则找出对应的值，否则我们将当前的nums[i]作为键，位置i作为值放进数组返回。代码如下:

public static int[] twoSum(int[] nums, int target) {
        int[] result = new int[2];
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            if (map.containsKey(target - nums[i])) {
                result[0]=map.get(target-nums[i]);
                result[1]=i;
            } else {
                map.put(nums[i], i);
            }
        }
        return result;
    }