Two-Sum

发表于 分类于 阅读次数：

原题：

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:

1
2
3
4
Given nums = [2, 7, 11, 15], target = 9,

Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].

中文：给定一个int数组nums和一个int整数target，数组中任意两个数的和等于target，返回这两个数的下标。

这题一看很简单的，最容易想到的实现方式就是遍历：

1
2
3
4
5
6
7
8
9
10
11
public int[] twoSum(int[] nums, int target) {
        int size = nums.length;
        for(int i=0;i<size;i++){
            for(int j= i+1;j<size;j++){
                if(target==nums[i]+nums[j]){
                   return new int[]{i,j};
                }
            }
        }
        throw new IllegalArgumentException("No two sum solution");
    }

测试一下，完美。提交后发现官方给了更好的2种解决方案。

再回头看下遍历的时间复杂度是 

1
O(n^2)

太高了，我们试着优化一下。

第二版：

我们使用HashMap，把数组中的数值和下标一一对应存到一个HashMap.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public int[] twoSum(int[] nums, int target) {
		HashMap<Integer, Integer> map = new HashMap<>();
		int size = nums.length;
		for (int i = 0; i < size; i++) {
			map.put(nums[i], i);
		}
		for (int i = 0; i < size; i++) {
			int comp = target - nums[i];
			if (map.containsKey(comp) && (map.get(comp) != i)) {
				return new int[] { i, map.get(comp) };
			}
		}
		throw new IllegalArgumentException("No two sum solution.");
	}

经过优化后，时间复杂度降为O(n)了。

第三版

对第二版中的代码再优化下，得到

1
2
3
4
5
6
7
8
9
10
11
12
public int[] twoSum3(int[] nums, int target) {
		HashMap<Integer, Integer> map = new HashMap<>();
		int size = nums.length;
		for (int i = 0; i < size; i++) {
			int comp = target - nums[i];
			if (map.containsKey(comp)) {
				return new int[] { map.get(comp), i };
			}
			map.put(nums[i], i);
		}
		throw new IllegalArgumentException("No two sum solution");
	}

。