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

这题要求找出一个序列中是否存在和为一个给定值的两个元素，比如[2,7,11,15]给定9，那么就是下标0,1的两个元素。我们可以使用2层循环来暴力求解，但是这样复杂度就是O(n^2)，所以我们使用map来解决这个问题，一般的map存放key-value,这次我们反过来，放value-key,这样可以通过map.containsKey(target-nums[i])来判断这个元素能否和已经在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