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

這題要求找出一個(gè)序列中是否存在和為一個(gè)給定值的兩個(gè)元素，比如[2,7,11,15]給定9，那么就是下標(biāo)0,1的兩個(gè)元素。我們可以使用2層循環(huán)來暴力求解，但是這樣復(fù)雜度就是O(n^2)，所以我們使用map來解決這個(gè)問題，一般的map存放key-value,這次我們反過來，放value-key,這樣可以通過map.containsKey(target-nums[i])來判斷這個(gè)元素能否和已經(jīng)在map中的元素組成target

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

python中直接使用字典來完成

class Solution(object):
    def twoSum(self, nums, target):
        map = {}
        for i in range(len(nums)):
            if target - nums[i] in map:
                return [map[target - nums[i]], i]
            map[nums[i]] = i