題目

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

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.

Example:

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

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

解答

C#

public class Solution {
    public int[] TwoSum(int[] nums, int target) {
        Dictionary<int, int> temp = new Dictionary<int, int>();
        for (int i = 0; i < nums.Length; i++)
        {
            int left = target - nums[i];
            if (temp.ContainsKey(left))
            {
                return new int[] { temp[left], i  };
            }
            if (!temp.ContainsKey(nums[i]))
            {
                temp.Add(nums[i], i);
            }
        }
        return null;
    }
}

結果

Runtime: 264 ms, faster than 81.11% of C# online submissions for Two Sum.

Memory Usage: 29.2 MB, less than 51.69% of C# online submissions for Two Sum.

Time Complexity: O(n)

Space Complextiy: O(n)

為什麼我要這樣做？

本來一開始我是使用暴力法──用兩個for迴圈去解決，但是這樣發現是O(n^2)後，就試圖用更好的方式去寫。

1. 用 for 迴圈計算 target 減去 nums 的 left(餘數)
2. 檢查 Dictionary 裡有沒有已存在的餘數
   • 如果有，則回傳 Dictionary 的餘數 array 裡的 index 及現在的 index
     • 因為 target = Dictionary[left] + nums[index]
   • 如果沒有，則記錄此次 餘數 及 index 到 Dictionary 裡
3. 如果都找不到就回傳 null

這樣我就可以用一個 for 迴圈邊算每個 nums 的餘數、邊找有沒有符合的答案。

以上就是這次 LeetCode 刷題的分享啦！
如果其它人有更棒的想法及意見，請留言或寄信(t4730@yahoo.com.tw) 給我。
那我們就下回見囉