算法：兩個數之和

文章目錄

• 題目
• 方法一：暴力破解
• 方法二：哈希表

給定一個整數數組 nums 和一個整數目标值 target，請你在該數組中找出 和為目标值 target 的那兩個整數，并傳回它們的數組下标。

你可以假設每種輸入隻會對應一個答案。但是，數組中同一個元素在答案裡不能重複出現。

你可以按任意順序傳回答案。

例子1：

輸入：nums = [2,7,11,15], target = 9
輸出：[0,1]
解釋：因為 nums[0] + nums[1] == 9 ，傳回 [0, 1] 。      

例子2：

輸入：nums = [3,2,4], target = 6
輸出：[1,2]      

通過枚舉每一個值尋找。

int* twoSum(int* nums, int numsSize, int target) {
    int i,j;
    int *result=NULL;
    for(i=0;i<numsSize-1;i++)
    {
        for(j=i+1;j<numsSize;j++)
        {
            if(nums[i]+nums[j]==target)
            {
                 result=(int*)malloc(sizeof(int)*2);
                 result[0]=i;
                 result[1]=j;
                 return result;
            }
        }
    }
    return result;
}      

總結： 該方法簡單但是時間複雜度為 O(n2)。空間複雜度為 O(1)O(1);運作速度慢且記憶體空間消耗大

struct hashTable {
    int key;
    int val;
    UT_hash_handle hh;
};

struct hashTable* hashtable;

struct hashTable* find(int ikey) {
    struct hashTable* tmp;
    HASH_FIND_INT(hashtable, &ikey, tmp);
    return tmp;
}

void insert(int ikey, int ival) {
    struct hashTable* it = find(ikey);
    if (it == NULL) {
        struct hashTable* tmp = malloc(sizeof(struct hashTable));
        tmp->key = ikey, tmp->val = ival;
        HASH_ADD_INT(hashtable, key, tmp);
    } else {
        it->val = ival;
    }
}

int* twoSum(int* nums, int numsSize, int target, int* returnSize) {
    hashtable = NULL;
    for (int i = 0; i < numsSize; i++) {
        struct hashTable* it = find(target - nums[i]);
        if (it != NULL) {
            int* ret = malloc(sizeof(int) * 2);
            ret[0] = it->val, ret[1] = i;
            *returnSize = 2;
            return ret;
        }
        insert(nums[i], i);
    }
    *returnSize = 0;
    return NULL;
}
      

執行結果：

複雜度分析：

• 時間複雜度：O(N)O(N)，其中 NN 是數組中的元素數量。對于每一個元素 x，我們可以 O(1)O(1) 地尋找 target - x。
• 空間複雜度：O(N)O(N)，其中 NN 是數組中的元素數量。主要為哈希表的開銷。