# LeetCode 1. Two Sum

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

## 題目大意

要從 array `nums` 中找出一對數字相加恰等於 `target`

> 題目有說只會剛好有一組答案

## 思考

### Algo 1

最直覺的方法就是暴力解：

遍歷 `nums` ，找出兩個數字相加恰等於 `target`

class Solution
{
public:
    vector<int> twoSum(vector<int> &nums, int target)
    {
        size_t n = nums.size();

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

然而 Follow-up 希望我們想一個時間複雜度低於 $O(n^2)$ 的演算法，所以還不能交卷

***

### Algo 2

剛才的找法乍看之下好像就已經直覺到不能再直覺了，~~這種題目竟然是 Easy？還題號 1？~~

但其實我們稍微改良一下雙迴圈，就能降低時間複雜度了

我們先把 `vec` 做個排序，讓他元素從小到大
然後我們用雙指針的方式，一個從頭開始掃，另一個從尾往回，找到相加等於 `target`就停，交卷

class Solution
{
public:
    vector<int> twoSum(vector<int> &nums, int target)
    {
        size_t n = nums.size();
        vector<pair<int, int>> vec;

        for (int i = 0; i < n; i++)
        {
            vec.emplace_back(nums[i], i);
        }

        sort(vec.begin(), vec.end());

        int i = 0, j = n - 1;

        while (i <= j)
        {
            if (vec[i].first + vec[j].first > target)
                j--;
            else if (vec[i].first + vec[j].first < target)
                i++;
            else
                break;
        }

        return {vec[i].second, vec[j].second};
    }
};

這個演算法的精隨在於從外往內移動指標，不斷縮小搜索範圍，與 algo 1 作對比，algo 1每次檢查完畢，若我們仍未找到所求，我們實際上只是從頭開始一步一步往前走， algo 1豈不是慢太多了嗎？

不過這個方法要確保數列是排序過的，我們假設排序要花費 $O(n\log n)$，建立`vec` 跟雙指標遍歷完都花 $O(n)$，總體而言時間複雜度在 $O(n\log n)$
挺不錯了，但這種題目總覺得好像能夠 $O(n)$ 內解決吧？讓我們再想想其他演算法

***

### Algo 3

剛才的方法已經很好了，但我們可以回到真正更直覺的方法(嗯？更直覺結果想不到還叫更直覺嗎...🤔

其實再仔細想想如果要你來挑數字，你會怎麼做？
例如：

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

你應該會是這樣思考的：

> 第一個挑2，2加另一個數字要是9，那個數字應該是7。找找看有沒有7......

根據這樣的找法我們可以得出 algo 3

class Solution
{
public:
    vector<int> twoSum(vector<int> &nums, int target)
    {
        unordered_map<int, int> numsMap;

        for (int i = 0; i < nums.size(); i++)
        {
            int temp = target - nums[i];

            if (numsMap.find(temp) != numsMap.end())
                return {numsMap[temp], i};

            numsMap[nums[i]] = i;
        }
    }
};

我們在遍歷的過程把元素及其位置記錄下來，如果 `target` 減掉當前的元素 `nums[i]` 有在紀錄表中，表示走到 `nums[i]` 時我們正好找到所求，交卷 (`temp` $+$ `nums[i]` $=$ `target`)

我們假設用 Hash table 查找的時間複雜度可以降低到 $O(1)$ 內解決，這個演算法最壞的情況就是我們要遍歷完數列一次，時間複雜度即 $O(n)$