Two Sum

題目

需求

1. 給定一個整數數組 nums 和一個整數 target，返回兩個數字的索引，使得它們相加等於 target。
2. 可以假設每個輸入只對應一種答案，且相同的元素不可以被重複利用。
3. 答案可以按任何順序返回。

範例

範例 1：
輸入：nums = [2,7,11,15], target = 9
輸出：[0,1]
解釋：因為 nums[0] + nums[1] == 9，我們返回 [0, 1]。

範例 2：
輸入：nums = [3,2,4], target = 6
輸出：[1,2]

範例 3：
輸入：nums = [3,3], target = 6
輸出：[0,1]

限制

2 <= nums.length <= 10^4
-10^9 <= nums[i] <= 10^9
-10^9 <= target <= 10^9

只存在一個有效答案。

Solution

暴力解

/*
1. 第一個迴圈，表示依序拿取每個位置的數值
2. 第二個迴圈，根據前一個迴圈拿到的數值，往後依序查詢，找到相加為 target 的數值
3. 如果找不到，使用第一個迴圈的下一個數值，重複執行上述動作，直到最後或是找到
*/
public int[] TwoSum_BruteForce(int[] nums, int target)
{
    for (var i = 0; i < nums.Length; i++)
    {
        for (var j = i + 1; j < nums.Length; j++)
        {
            if (nums[i] + nums[j] == target)
            {
                return [i, j];
            }
        }
    }

    return [0, 0];
}

優化

/*
1. 第一個迴圈，表示依序拿取每個位置的數值
2. 從 Dictionary 找看看是否有數值符合相加為 target 的內容
2.1 沒有 -> 把現有的數值和索引位置，當作 KeyValue Pair，存到 Dictionary 內
2.2 有   -> 返回索引
*/
public int[] TwoSum_Hash(int[] nums, int target)
{
    var dc = new Dictionary<int, int>();
    for (var i = 0; i < nums.Length; i++)
    {
        var hasValue = dc.TryGetValue(target - nums[i], out var index);
        if (hasValue)
        {
            return [i, index];
        }

        dc[nums[i]] = i;
    }

    return [0, 0];
}

複雜度分析

Complexity	BruteForce	HashTable
Time Complexity	$O(N^2)$	$O(N)$
Space Complexity	$O(1)$	$O(N)$

Reference

https://leetcode.com/problems/two-sum/description/
https://leetcode.com/problems/two-sum/solutions/4838454/c-c-two-friendly-solutions-for-beginners-clear-and-concise/