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].
分析¶
使用哈希表,当遍历数组的时候,把数组元素的互补target - nums[i]
和当前下标(i
)插入到哈希表中,当数组元素已经存在于哈希表中时,说明找到了答案,返回哈希表值和当前下标。
public static int[] twoSum(int[] nums, int target) { if (nums == null || nums.length < 2) return new int[]{}; Map<Integer, Integer> map = new HashMap<>(); for (int i = 0; i< nums.length; i++) if (map.containsKey(nums[i])) return new int[]{map.get(nums[i]), i}; else map.put(target - nums[i], i); return new int[]{}; }
def twoSum(self, nums, target): """ :type nums: List[int] :type target: int :rtype: List[int] """ result = {} index = 0; for i in nums: if i in result: return [index, result[i]] else: result[target-i] = index index += 1;
近期评论