P001-Two-Sum

Mar 15, 2017 | LeetCode

P001 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.

Example:

Given nums = [2, 7, 11, 15], target = 9,
Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].

思路

遍历两次(嵌套循环)太慢。
考虑将出现过的数字记录到map中。要返回index，所以连值和index一并记录，故选择map.
遍历时若当前数字能和map中的值构成target则返回,否则将当前值置于map中。

代码

java

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

python

class Solution001(object):
    def twoSum(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[int]
        """
        m = {}
        for (index, value) in enumerate(nums):
            if (target - value) in m:
                return (index, m[target - value])
            m[value] = index

LeetCode