001.md

001. 两数和 - Two Sum

[Hash Tables]

Problem Link

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].

class Solution {
    public int[] twoSum(int[] nums, int target) {
        Map<Integer, Integer> map = new HashMap<>();
        for(int i = 0; i < nums.length; i++)
            map.put(nums[i], i);
        int complement = 0;
        for(int i = 0; i < nums.length; i++){
            complement = target - nums[i];
            if(map.containsKey(complement) && map.get(complement) != i)
                return new int[] {i, map.get(complement)};
        }
        throw new IllegalArgumentException("No two sum solution");
    }
}

复杂度分析：11ms

• 时间复杂度：O(n)O(n)， 我们只遍历了包含有 nn 个元素的列表一次。在表中进行的每次查找只花费 O(1)O(1) 的时间。
• 空间复杂度：O(n)O(n)， 所需的额外空间取决于哈希表中存储的元素数量，该表最多需要存储 nn 个元素。

Other Solution

class Solution {
    int size = 2048;
	int[] map = new int[size];
	int length = 2047;
	int index;
    
    public int[] twoSum(int[] nums, int target) {
        for (int i = 0; i < nums.length; i++) {
			index = nums[i] & length;
			if (map[index] != 0) {
				return new int[] { map[index] - 1, i };
			} else {
				map[(target - index) & length] = i + 1;
			}
		}
		throw new IllegalArgumentException("No two sum solution");
    }
}

复杂度分析：2ms

• 时间复杂度：O(n)