LeetCode 1 -TwoSum_Solution (Coding With C#)

題目:

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

那麼我也只需要查訪一次陣列就可以找到對應的陣列索引了。

剛開始練習有誤請指教,謝謝。