Two Sum

Problem: Two Sum

Once we use hash table, the solution to this problem seems quite clear. During reading lists, we store the distance between read number and target number as key and index as value in hash table. We can do search while reading. If we get a research result, it means that the value of found entry add our current number equals target. Then we return 2 index.

Code in Python:

class Solution(object):
    def twoSum(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[int]
        """
        numdict = {}
        for i in xrange(0, len(nums)):
            if nums[i] in numdict:
                return [numdict[nums[i]], i+1]
            else:
                numdict[target-nums[i]] = i+1

Code in Java:

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