You've successfully subscribed to The Daily Awesome
Great! Next, complete checkout for full access to The Daily Awesome
Welcome back! You've successfully signed in.
Success! Your account is fully activated, you now have access to all content.
Success! Your billing info is updated.
Billing info update failed.

001. 两数和 - Two Sum

. 1 min read

001. 两数和 - Two Sum

[Hash Tables]

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)