Two Sum

https://leetcode.com/problems/two-sum/description/

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.

Thoughts

思路实际和背包很像，看是否能选几个元素凑够特定的数。只是它规定了只选了两个物品，因此比背包简单，不需要双重循环。

Code

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

        return res;
    }
}

Analysis

Errors:

1. 由于不是排好序的，因此不能直接使用2 sum。

时间复杂O(n), 空间复杂度O(n).