Two Sum

#1.Two Sum

Problem statement

Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target.

You may assume that each input would have exactly one solution, and you may not use the same element twice.

You can return the answer in any order.

Example 1

Input: nums = [2,7,11,15], target = 9
Output: [0,1]
Explanation: Because nums[0] + nums[1] == 9, we return [0, 1].

Example 2

Input: nums = [3,2,4], target = 6
Output: [1,2]

Example 3

Input: nums = [3,3], target = 6
Output: [0,1]

Explanation

從給定的 array 中找到兩個數相加等於 target，並且返回兩數索引

• 只會有一個有效答案
• 同一個元素不會使用兩次
• 可以返回任何順序的索引

Solution

比較直覺地方式是使用雙迴圈迭代陣列來解，這種暴力解法遇到資料量較大時，需要更多時間來完成。

如果以時間複雜度作為考量，需設法減少迴圈的使用次數，讓執行時間大幅下降，那麼可使用一個額外空間來儲存元素，以達到空間換時間的想法，雖然此方法讓時間複雜度降低，同時也提高了空間複雜度。

Array
透過雙迴圈逐一走訪陣列，因為元素不可重複，故取 i+1 略過自己以及計算過的值

public int[] TwoSum(int[] nums, int target)
{
    int i, j;

    for (i = 0; i < nums.Length; i++)
        for (j = i + 1; j < nums.Length; j++)
            if (nums[i] + nums[j] == target)
                return new int[] { i, j };

    return null;
}

HashTable
使用一個額外空間 HashTable，以達到用空間換取時間

public int[] TwoSum(int[] nums, int target)
{
    Hashtable hash = new Hashtable();

    for (int i = 0; i < nums.Length; i++)
    {
        int num = nums[i];
        int diff = target - num;

        if (hash.ContainsKey(diff))
            return new int[] { i, (int)hash[diff] };

        if (!hash.ContainsKey(num))
            hash.Add(num, i);
    }

    return null;
}

Dictionary
一樣使用一個額外空間 Dictionary 達到空間換時間的目的

public int[] TwoSum(int[] nums, int target)
{
    Dictionary<int, int> dic = new Dictionary<int, int>();

    for (int i = 0; i < nums.Length; i++)
    {
        int num = nums[i];
        int diff = target - num;

        if (dic.ContainsKey(diff))
            return new int[] { i, (int)dic[diff] };

        if (!dic.ContainsKey(num))
            dic.Add(num, i);
    }

    return null;
}

---

Reference

LeetCode Solution

GitHub Repository

---

Thanks for reading the article 🌷 🌻 🌼

If you like it, please don't hesitate to click heart button ❤️
or click like on my Leetcode solution
or follow my GitHub ⭐ I'd appreciate it.

---