描述

给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。

你可以假设每种输入只会对应一个答案。但是，你不能重复利用这个数组中同样的元素。

示例:

给定 nums = [2, 7, 11, 15], target = 9

因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]

Python3

利用一次遍历和dict

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        mapping = {}
        for index,num in enumerate(nums):
            if target-num in mapping:
                return [index,mapping[target-num]]
            else:
                mapping[num]=index
        return []

Java

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

for循环的时间复杂度是O(n)，整个程序的时间复杂度就是O(n)