[TOC]

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