[Leetcode] Two Sum

Problem

Given an array of integers, find two numbers such that they add up to a specific target number.

The function twoSum should return indices of the two numbers such that they add up to the target, where index1 must be less than index2. Please note that your returned answers (both index1 and index2) are not zero-based.

You may assume that each input would have exactly one solution.

Input: numbers={2, 7, 11, 15}, target=9
Output: index1=1, index2=2

Analysis

• 用一个hash表来围护每个数和其对应的index
• 如果有重复的数字，则overwrite， 即保留最后出现的index
• 然后遍历所有的数，如果 （target - 当前数）在哈希表中，且俩数的index不一样，则找到解了
• 复杂度
• Time: O(n)
• Space: O(n)

Code

	public class Solution {
	public int[] twoSum(int[] nums, int target) {
	//put each number and its index in hashmap
	//overwrite repeated numbers
	HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
	for(int i=0; i<nums.length; i++){
	map.put(nums[i], i);
	}
	//for each number, check whether (target-remain) is in the map
	//make sure two indexes are different
	for(int i=0; i<nums.length; i++){
	int remain = target - nums[i];
	if(map.containsKey(remain) && map.get(remain)!=i){
	int[] rnt = new int[2];
	rnt[0] = i+1;
	rnt[1] = map.get(remain)+1;
	return rnt;
	}
	}
	return null;
	}
	}

view raw two-sum.java hosted with ❤ by GitHub

Reference
[1] https://leetcode.com/problems/two-sum/