Problem

Input:

• Array of Nums
• Target

Output:

• Array of 2 elements

Constraints:

• $2 <= nums.length <= 10^3$
• $10^9 <= nums[i] <= 10^9$
• $10^9 <= target <= 10^9$
• Only one valid answer exists.

For Example:

Example 1:

Input: nums = [2,7,11,15], target = 9
Output: [0,1]
Output: 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]

Solution

Brute-force search

判斷nums中的各種組合( n(n-1) )是否和target相等，若相等，則Output。

C實作

/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
int* twoSum(int* nums, int numsSize, int target, int* returnSize){

    *returnSize = 2; //Tell Leetcode that we return 2 elements Array
    int *result = malloc( sizeof(int) * 2 ); //Create 2 elements Dynamic Array

    for (int i = 0; i < numsSize - 1; i++) //Search from the 1st nums'value
        for (int j = i + 1; j < numsSize; j++) //Check if there's match value or not
        {
            if ( target == nums[i] + nums[j] )
            {
                result[0] = i;
                result[1] = j;
                return result;
            }

        }

    return result;
}

Hash Table

因為C並不包含STL，因此建議使用C++內的STL資料庫Unordered Map來實現此方法

1.建立Table(nums.value做為key，將nums.index作為value)
2.開始查找nums.value，並確認 Taget - (nums.value)是否存在Table中
    2-1.若存在，則輸出 nums.index 和 Table[Target - (nums.value)]的value
    2-2.若不存在，則將nums添加進Table中，持續第二步驟直到找到為止

C++實作

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

        vector<int> result;
        unordered_map<int,int> umap;

        for(int i = 0; i < nums.size(); i++)
        {
            if( umap.find(target-nums[i]) == umap.end()) //Do not find key
            {
                umap[nums[i]] = i;
            }
            else
            {
                result.push_back(umap[target-nums[i]]);
                result.push_back(i);
                break;
            }            
        }        
        return result;
    }
};