我的吉米城: [LeetCode] Two Sum 兩兩相加 (No.1)

2016/7/13

[LeetCode] Two Sum 兩兩相加 (No.1)

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.

Example:

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

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

UPDATE (2016/2/13):
The return format had been changed to zero-based indices. Please read the above updated description carefully.

Ref: https://leetcode.com/problems/two-sum/

中文簡單說明：
給你的個數列，要你找出唯一的一組數字相加等於目標值，而這數列是從0計算的。
要注意的是，數列裡的數字有可能會重覆！

解法：
因為只有一個解，所以我們可以用個很簡單的方法來求答案，就是直接用目標值減去我們選擇的數列其中一數字，再看看該其他數字是否可找到該答案，如果有，就是那組數字，求出位置即可。

部份程式碼：

	public int[] twoSum(int[] nums, int target) {
	for (int i = 0; i < nums.length; i++) {
	int num = nums[i];
	if (getTargetIndex(nums, target - num, i) != -1) {
	return new int[] { i, getTargetIndex(nums, target - num, i) };
	}
	}
	return new int[] { 0, 0 };
	}
	public int getTargetIndex(int[] nums, Integer target, Integer exceptIndex) {
	for (int i = 0; i < nums.length; i++) {
	if (i == exceptIndex) {
	continue;
	}
	if (nums[i] == target) {
	return i;
	}
	}
	// 找不到，回傳-1
	return -1;
	}