如果什麼都沒準備，以 Abandon Two Sum 來說

這邊聽我娓娓道來第一次使用 LeetCode 的情境：

註冊 LeetCode 帳號成功、點選 Problems 後，印入眼簾的是一千多題，不懂門路的我，想說過往寫題目都從第一題開始，而且難度標注是 Easy，應該是沒問題可以順利解決，於是點擊 Tow Sum。

題目的內容是這樣：

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]
Output: Because nums[0] + nums[1] == 9, we return [0, 1].

菜雞的我，想一下後認為使用兩個 for loop 就能處理了。所以我寫出這樣的程式碼：

const twoSum = (nums, target) => {
  for (let i = 0; i < nums.length; i++) {
    for (let j = i + 1; j < nums.length; j++) {
      if (nums[j] = target - nums[i]) {
        return [i, j];
      }
    }
  }

  return [];
}

開心地按下 Submit 後，得到

Status: Runtime Error

當下只有無限的問號在我腦中，奇怪，這樣做不對嗎？

重新來一遍，會如何分析 Two Sum

首先要仔細閱讀已知的資訊，除了閱讀題目本身的描述外，點擊 Related Topics 後會看到 Array & Hash Table。對於菜雞來說，關於如何操作 Array 有個基本的概念，但是 Hash Table 就不太理解，於是找尋 Hash Table 的相關資訊，大致上有概念後，會陷入一個窘境，如何實作？

想了 20 分鐘後仍然沒頭緒，直接找答案。了解 Hash 除了常用於密碼學上，也可以應用在其他情境。在參考解答後寫了 JS 的版本：

const twoSum = (nums, target) => {
    const comp = {};

    for (let i=0; i<nums.length; i++){
        if (comp[ nums[i] ] >= 0 ) {
            return [ comp[nums[i] ], i]
        }

        comp[target-nums[i]] = i
    }
};

說實在的，看答案後重新寫出來並不可恥，重點是學習這個問題背後要測試的技術是什麼，這邊只使用一次 for loop，每次進行判斷與製作 Hash Table，所以可以有效地壓縮搜尋時間。

完成基本功的我想要增加其他訓練

因為工作上的需求，除了平常使用 JS 開發之外，有時需要接觸 Java 與 C。趁這個機會同一題用三種語言寫寫看，藉此了解三個語言不同之處。

Java

class Solution {
    public int[] twoSum(int[] nums, int target) {
        HashMap<Integer, Integer> m = new HashMap<Integer, Integer>();
        int[] answer = new int[2];

        for (int i = 0; i < nums.length; ++i) {
            if (m.containsKey(target - nums[i])) {
                answer[0] = i;
                answer[1] = m.get(target - nums[i]);
                break;
            }

            m.put(nums[i], i);
        }

        return answer;
    }
}

可以看出，這題因為需要的觀念是 Array 與 Hash Table，JS 與 Java 在這部分的幾乎類似，因此程式碼十分相近。

C

直覺作答，使用兩個 for-loop

int *twoSum(int *nums, int numsSize, int target, int *returnSize)
{
    int *result = malloc(sizeof(*result) * 2);
    int x, y;

    for (x = 0; x < numsSize; x++)
    {
        for (y = x + 1; y < numsSize; y++)
        {
            if ((nums[x] + nums[y] == target))
            {
                *returnSize = 2;
                result[0] = x;
                result[1] = y;
                return (result);
            }
        }
    }

    return (NULL);
}

參考 Submission 後嘗試製作 Hash Table

#define SIZE 50000

int hash(int key)
{
    int r = key % SIZE;
    return r < 0 ? r + SIZE : r;
}

void insert(int *keys, int *values, int key, int value)
{
    int index = hash(key);

    while (values[index])
    {
        index = (index + 1) % SIZE;
    }

    keys[index] = key;
    values[index] = value;
}

int search(int *keys, int *values, int key)
{
    int index = hash(key);

    while (values[index])
    {
        if (keys[index] == key)
        {
            return values[index];
        }

        index = (index + 1) % SIZE;
    }

    return 0;
}
int *twoSum(int *nums, int numsSize, int target, int *returnSize)
{
    *returnSize = 2;
    int keys[SIZE];
    int values[SIZE] = {0};

    for (int i = 0; i < numsSize; i++)
    {
        int complements = target - nums[i];
        int value = search(keys, values, complements);

        if (value)
        {
            int *indices = (int *)malloc(sizeof(int) * 2);
            indices[0] = value - 1;
            indices[1] = i;
            return indices;
        }

        insert(keys, values, nums[i], i + 1);
    }

    return NULL;
}

我得承認，C 的處理方式跟上面兩個語言非常不同。撰寫過程中因為不了解只好再去找一次解答，了解更多 C 的相關運用。
這邊看到幾個版本：

• 直接使用 for-loop 解題，玩味的地方在於 C 不會出現 Runtime Error。
• 使用 struct 模擬 JS & Java 的物件好製作 Hash Table，接著使用 two pointer 的找尋答案。
• 不使用 struct，而是用 Array 模擬物件製作 Hash Table，再用 for-loop 一個一個找尋。

C 實在是太有趣了，同一題居然有多種寫法，而且執行的結果跟 JS 有不小的差距。

結語

從不能用暴力解（Brute Force）這件事來看，LeetCode 希望大家寫出有效率的運作模式。而有效率到底該怎麼判斷？這就是明天要討論的事情。