[碼農] Leetcode #1 Two Sum (C/C++) 解題範例

題目

Given an array of integers, return indices of the two numbers such that they add up to a specific target.

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

( from Leetcode #1 Easy problem)

範例

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

Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].

 

轉載請標明原文出處: Leetcode #1 Two Sum (C/C++) 解題範例

解法1: C  by Brute Force(暴力法)

 
/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
#define RETURN_ARRAY_SIZE 2
int* twoSum(int* nums, int numsSize, int target) {
    int i,j;
    int* returnArray = calloc(RETURN_ARRAY_SIZE, sizeof(int));
    
    for (i=0; i<numsSize;i++){
        for (j=i+1; j<numsSize;j++){
            if ((nums[i]+nums[j])==target){
                returnArray[0]= i;
                returnArray[1]= j;
            }
        }
    }    
    return returnArray;
}

 解說

遍歷所有可能找出解答。

時間複雜度:O(n2
空間複雜度:O(1)

Note

  1. 執行時間為 76 ms
  2. malloc() 與 calloc()的差異可以參考這篇文章

解法2:C++ by One-pass Hash Table

 
class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        vector<int> ans;
        map <int, int> hashMap;
        map <int, int>::iterator iter;
        
        for (int i=0; i<nums.size();i++){
            iter = hashMap.find(target-nums[i]);  
            
            if (iter != hashMap.end()){
                ans.push_back(iter->second);
                ans.push_back(i);
                return ans;
            }
            else
                hashMap.insert(pair<int,int>(nums[i], i)); 
        }
        return ans;
    }
};

 

 解說

建立Hash table,同時比對Hash table內是否有對應的答案存在,由於假設只有唯一解,所以找到即是答案。

時間複雜度:O(n),因為Hash table讓 look-up time為 O(1),所以整體複雜度從O(n2) 減為O(n)。
空間複雜度:O(n),Hash table多需要的儲存空間。

Note

  1. 執行時間為 8 ms
  2. Hash table的說明可以參考這篇文章
  3. Vector 與 iterator的用法可以參考這篇文章