題目:
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.
題目大意:
給予一串數值陣列,以及一個目標值。得到兩個陣列索引位子,而該索引位子的數值相加會等於目標值。
並且給予的數值陣列只可查訪一次,不可多次查訪。
分析:
[ 2, 7, 11, 15, ]
Target = 9
從第二句話可以看出來,陣列只可以跑一次迴圈。
也就是要符合時間複雜度O(n)的情況。
在第一次嘗試先不管時間複雜度來寫了話如下:
public int[] TwoSum(int[] Nums,int Target)
{
for(int i = 0 ; i <= Nums.Length; i++)
{
for(int x = i+1; x <= Nums.Length; i++)
{
if(Nums[i] == (Target-Nums[x]))
{
return new int[] {i,x};
}
}
}
throw new Exception("Error");
}
跑兩次迴圈查詢,第一圈查詢為基準值,第二圈是檢驗值。
基準值如果等於目標值減去檢驗值相等了話,就證明基準值加上檢驗值會等於目標值
數學式如下:
X = Target - Y => Target = X +Y
問題是這樣程式設計出來的時間複雜度會是O(n2)這樣不符合題目的O(n)
所以調整一下程式碼如下:
public int[] TwoSum(int[] nums, int target)
{
Dictionary<int, int> TempData = new Dictionary<int, int>();
for (int i = 0; i <= nums.Length; i++)
{
if (TempData.ContainsKey(target - nums[i]))
{
return new int[] { TempData[target - nums[i]], i };
}
TempData.Add(nums[i], i);
}
return new int[] { 0, 0 };
}
修改成採用 Dictionary 去儲存數值,而每次去檢查Target減去基準值,是不是我字典裡的KEY值有包含。
Key = Target - 基準值 => 基準值 + KEY = Target
那麼我也只需要查訪一次陣列就可以找到對應的陣列索引了。
剛開始練習有誤請指教,謝謝。