LeetCode-(1) Two Sum

 問題位址：https://oj.leetcode.com/problems/two-sum/

問題描述： Given an array of integers, find two numbers such that they add up to a specific target number.

The function twoSum should return indices of the two numbers such that they add up to the target, where index1 must be less than index2. Please note that your returned answers (both index1 and index2) are not zero-based.

You may assume that each input would have exactly one solution.

Input: numbers={2, 7, 11, 15}, target=9

Output: index1=1, index2=2

思路：

1.因為隻有唯一解，是以任意兩個元素和為唯一進制素。最先想到的是，窮舉法，把所有2個元素相加，則得到一個值，如果是Target，則得到解。該方法可行。 判斷該方法的複雜度：1+2+3+4+5+...+n=

 ,即 

。 考慮有沒有更快的方法： 2.通過Target減去數組元素，然後得到被減數，在數組中查找。通過Target減去一個元素，然後在剩餘元素中取查找被減數。這樣好像更友善，但是其實和上面方法1的複雜度是一樣的，即 。 3.空間換時間，在方法2的基礎上，如果能把在剩餘元素中查找的複雜度從O(n)變為O(1)，整體複雜度就會從

變到O(n)。如果把查找變為O(1)呢，當然是Hash表了。因為要傳回元素的小标，是以，這裡用了hashMap，如果不需要下标，隻需要2個元素的值，則可以用HashSet。OK，方法正确。開始實作。

幾點注意事項：

1）因為需要小标，所有Map的key是元素的值，Value應該是小标，是以Map應該是 Map<int,int>。但是存在這樣的問題，可能存在值相同的元素，這樣的話Key相同，之前的下标會被覆寫掉。是以Value應該是一個連結清單或者數組，下面的code中用了Arraylist。 2）注意小标是從1開始的。 3）要求index1 must be less than index2，是以周遊的時候從0~n周遊。 4）如果是T=X+X這樣情況，要避免找到相同的第一個小标，所有要跳過自己。

 Code:

public int[] twoSumNotSame(int[] numbers, int target) {
		int[] a = new int[2];
		HashMap<Integer, ArrayList<Integer>> map = 
new HashMap<Integer, ArrayList<Integer>>(numbers.length);
		for (int i = 0; i < numbers.length; i++) {
			if (map.get(numbers[i]) == null) {
				ArrayList<Integer> list = new ArrayList<Integer>();
				list.add(i);
				map.put(numbers[i], list);
			} else {
				map.get(numbers[i]).add(i);
			}
		}

		ArrayList<Integer> rsList = null;
		int firstIndex = 0;
		for (int i = 0; i < numbers.length; i++) {
			if (map.get(target - numbers[i]) != null) {
				rsList = map.get(target - numbers[i]);
				if (rsList.size() == 1 && rsList.get(0) == i) {
					continue;
				}
				firstIndex = i;
				break;
			}
		}
		int secondIndex = 0;
		for (Integer e : rsList) {
			if (e != firstIndex) {
				secondIndex = e;
				break;
			}
		}
		a[0] = firstIndex + 1;
		a[1] = secondIndex + 1;
		return a;
	}
           

 UT:

@Test
	public void t1NotEquals() {
		int[] numbers = { 2, 7, 11, 15 };
		int target = 9;
		int[] a = solution.twoSumWithSame(numbers, target);
		Assert.assertEquals(1, a[0]);
		Assert.assertEquals(2, a[1]);

	}

	@Test
	public void t2NotEquals2() {
		int[] numbers = { 20, 4, 11, 15, 3, 5, 9 };
		int target = 13;
		int[] a = solution.twoSumWithSame(numbers, target);
		Assert.assertEquals(2, a[0]);
		Assert.assertEquals(7, a[1]);

	}

	@Test
	public void t3Equals() {
		int[] numbers = { 2, 4, 6, 7 };
		int target = 8;
		int[] a = solution.twoSumWithSame(numbers, target);
		Assert.assertEquals(1, a[0]);
		Assert.assertEquals(3, a[1]);

	}

	@Test
	public void t4Equals2() {
		int[] numbers = { 2, 4, 6 };
		int target = 12;
		int[] a = solution.twoSumWithSame(numbers, target);
		Assert.assertEquals(3, a[0]);
		Assert.assertEquals(3, a[1]);

	}
           

  思考：      空間換時間是一種常用的方法，可以通過緩存資料，或者做映射，來降低時間複雜度。