LeetCode 001 Two Sum

LeetCode 001 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:

<pre>Given nums = [2, 7, 11, 15], target = 9,

Because nums[0] + nums[1] = 2 + 7 = 9, return [0, 1]. </pre>

题目大意：

给定一个整数数组，从中找出两个数的下标，使得它们的和等于一个特定的数字。可以假设题目有唯一解。

解题思路：

1. 最简单的思路是暴力法，两重循环试遍所有组合。
2. 先排序，再用两指针法，若指针指向的数和小于target则左指针右移，反之亦然。注意，为了保持原数组的下标，要预先保留下标及值对到Node中。
3. 遍历数组，同时查看target-该数是否在HashMap中，否则加入到HashMap中。

Python代码：

def twoSum(self, nums: List[int], target: int) -> List[int]:
	for i in range(len(nums)):
		for j in range(i + 1, len(nums)):
			if nums[i] + nums[j] == target:
				return [i, j]

def twoSum(self, nums: List[int], target: int) -> List[int]:
	temp.sort()
	i, j = 0, len(temp) - 1
	while i < j:
		if temp[i][0] + temp[j][0] < target:
			i += 1
		elif temp[i][0] + temp[j][0] > target:
			j -= 1
		else:
			return [temp[i][1], temp[j][1]]

def twoSum(self, nums: List[int], target: int) -> List[int]:
	nums_dict = {}
	for i, n in enumerate(nums):
		if target - n in nums_dict:
             return [nums_dict[target - n], i]
		nums_dict[n] = i

第二种方法，Python的tuple相当于Java的自定义Node，但节省了很多代码。每种方法都大概节省了2/3的代码。

Java代码：

public int[] twoSum0(int[] nums, int target) {
	int[] re = new int[2];
	for(int i=0;i<nums.length;i++)
		for(int j=i+1;j<nums.length;j++){
			if(nums[i]+nums[j]==target){
				re[0] = i;
				re[1] = j;
				return re;
			}
				
		}
	return re;
}

public int[] twoSum2(int[] nums, int target) {
	Node[] ary = new Node[nums.length];
	for(int i=0;i<nums.length;i++){
		ary[i] = new Node(i, nums[i]);
	}
	
	Arrays.sort(ary, new Comparator<Node>() {
		@Override
		public int compare(Node o1, Node o2) {
			return o1.value - o2.value;
		}
	});
	int[] re = new int[2];
	int start=0, end=nums.length-1;
	while(start<end){
		if(ary[start].value+ary[end].value==target){
			re[0] = ary[start].index;
			re[1] = ary[end].index;
			return re;
		}
		else if(ary[start].value+ary[end].value<target)
			start++;
		else
			end--;
	}
	return re;
}

class Node {
	Node(int i, int v){
		this.index = i;
		this.value = v;
	}
	int index;
	int value;
}

public int[] twoSum(int[] nums, int target) {
	HashMap<Integer,Integer> h  = new HashMap<Integer,Integer>();
	
	int[] re = new int[2];
	for(int i=0;i<nums.length;i++){
		Integer index = h.get(target-nums[i]);
		if(index!=null){
			re[0]=index;
			re[1]=i;
			return re;
		}
		h.put(nums[i],i);
	}
	return re;
}

算法分析：

1. 时间复杂度为<code>O(n²)</code>，空间复杂度O(1)。
2. 时间复杂度为O(nlogn)，空间复杂度O(n)。
3. 时间复杂度为O(n)，空间复杂度O(n)。