TwoSum [source code]

public class TwoSum {
static
/******************************************************************************/
public class Solution {
    public int[] twoSum(int[] nums, int target) {
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            Integer other = map.get(target - nums[i]);
            if (other == null) {
                map.put(nums[i], i);
            } else {
                return new int[]{other, i};
            }
        }
        return new int[0];
    }
}
/******************************************************************************/

    public static void main(String[] args) {
        TwoSum.Solution tester = new TwoSum.Solution();
        int[] i1n1 = {};
        int i1t1 = 17;
        Printer.array (tester.twoSum(i1n1, i1t1));
    }
}

2sum 也没什么好说的了, 虽然算法本身非常的有启发性. 最后的速度是8(78);

editorial里面最后当找不到的时候是 throw new IllegalArgumentException("No two sum solution");. 不知道实际面试的时候会不会这样考察 exception;

discussion里面好像有人先直接 sort, 然后2pointers 做, 最后 OJ 给的速度好像比 map 的要高, 不过这个没有必要刻意追求;

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

这个是可以写的更短的一个写法;

关于复杂度的一点caveat:

In C++, the running time of map's get is O(logn), not O(1). In Java, we have O(1) get, so it's O(n).

Problem Description

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].
Difficulty:Easy
Category:Algorithms
Acceptance:33.81%
Contributor: LeetCode
Companies
linkedin uber airbnb facebook amazon microsoft apple yahoo dropbox bloomberg yelp adobe
Related Topics
array hash table
Similar Questions
3Sum 4Sum Two Sum II - Input array is sorted Two Sum III - Data structure design Subarray Sum Equals K