#1 Two Sum

題目

給予一組陣列和一個整數目標，回傳陣列中兩個相加起來等於目標值的數字的位置。可以假設每一組輸入只會有一組解，並且不能使用同樣的陣列元素兩次。回傳的結果可以是任意排序的。

限制條件

1. 選定的兩個陣列中的數字相加起來要等於目標。
2. 每一個輸入只會有唯一解。
3. 選定的兩個數字不能是陣列中的同一個位置上的數字。
4. 回傳的結果可以任意排序。
5. 2 <= 陣列大小 <= 10^4
6. -10^9 <= 陣列元素數值 <= 10^9
7. -10^9 <= 整數目標值 <= 10^9

解題思路

Brute Force

最直覺的方式是將每一個數字都配對過一遍，找到答案。

利用第一個for迴圈選擇第一個數字，然後利用第二個for迴圈選擇第二個數字，兩個數字相加起來如果等於目標值，則回傳兩個數字的位置。

public class Solution {
	public int[] TwoSum(int[] nums, int target){
			//排除不符合條件的數值
			if(nums.Length<2 || nums.Length>10000) return new int[2]{0,0};
      if(target<-1000000000||target>1000000000) return new int[2]{0,0};
			//
			for(int i=0;i<nums.Length-1;i++){
				for(int j=i+1;j<nums.Length;j++){
					if(nums[i]+nums[j]==target) return new int[2]{i,j};
				}
			}
			return new int[2]{0,0};
	}
}

複雜度分析：

• 時間複雜度：由於用了兩個for迴圈組成的巢狀迴圈，最壞的情況下花費的時間是(n-1)*(n-1)，複雜度為O(n^2)。
• 空間複雜度：沒有使用任何會讓空間成長的資料結構，因此複雜度為O(1)。

Follow-up

使用時間複雜度小於O(n^2)的演算法來解答。

Hash Table

每一次當我們挑選一個數字時，將它和目標值相減，就會得到需要的另外一個數字。如果我們將這個數字記錄下來，當我們遇到的時候，就可以馬上知道這是我們要的答案。

透過Hash Table，記錄當下挑選的數字所需要的另外一個數字和當下數字的位置，當碰到相對應的需要的數字時，就可以從Hash Table中取出記錄下的數字位置，與現在需要的數字位置，組合成答案。

public class Solution {
	public int[] TwoSum(int[] nums, int target){
			//排除不符合條件的數值
			if(nums.Length<2 || nums.Length>10000) return new int[2]{0,0};
      if(target<-1000000000||target>1000000000) return new int[2]{0,0};
			//
			var ht = new Hashtable();
			//
			for(int i=0;i<nums.Length;i++){
				if(ht.Contains(nums[i])) {
					return new int[2]{(int)ht[nums[i]],i};
				}
				int val = target - nums[i];
				if(!ht.Contains(val))	ht.Add(val,i);				
			}
			return new int[2]{0,0};
	}
}

複雜度分析：

• 時間複雜度：由於只用了一個for迴圈，並且Hash Table的加入與查詢花費的時間都是O(1)，最壞的情況下花費的時間是(n-1)*(n-1)，複雜度為O(n^2)。
• 空間複雜度：Hash Table花費的空間會隨著加入的元素而增加，在最壞的情況下會加入n-1元素，複雜度為O(n)。

學習重點

• 空間換時間：利用增加空間來換取降低時間複雜度。
• Hash Table：如何使用Hash Table來記錄資料，並且快速的從中取得資料，提高計算效率。