leetcode（1）: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].

题意简单明了。就是返回求和的两个数的索引。假设输入有唯一解。

实现：

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

        int[] res = new int[2];

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

            int a = nums[i];

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

                if (j != i) {

                    int b = nums[j];

                    if (a + b == target) {

                        res[0] = i;

                        res[1] = j;

                    }

                }

            }

        }

        return res;

    }

。。。提交后发现
Runtime: 74 ms, faster than 5.14% of Java online submissions for Two Sum.
Memory Usage: 38.6 MB, less than 38.09% of Java online submissions for Two Sum.
发现和提交者对比后这个算法的性能低到不行。大约O（n^2）果然最容易想到的往往都是最坑的。

后面查看大神们的思路后的HashMap实现：

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

看来还是得多思考，最后结果：
Runtime: 3 ms, faster than 99.36% of Java online submissions for Two Sum.
Memory Usage: 39.2 MB, less than 22.78% of Java online submissions for Two Sum.