两数之和¶

难度：简单
链接：https://leetcode-cn.com/problems/two-sum/

标签：Array, Hash Table

描述¶

给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那两个整数，并返回他们的数组下标。

你可以假设每种输入只会对应一个答案。但是，数组中同一个元素不能使用两遍。

示例:

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

因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]

题解¶

暴力枚举¶

根据题意，最简单粗暴的思路就是双for循环遍历，在前后两数之后等于target时break。

C

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

Python3

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        n = len(nums)
        for i in range(n):
            for j in range(i+1, n):
                if (nums[i] + nums[j]) == target:
                    return [i,j]
        return []

时间复杂度：\(O(N^2)\)
空间复杂度：\(O(1)\)

如果考虑nums不包含满足条件的情况，需要修改以上C代码

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

哈希表¶

第二种方式是使用哈希表，使用C语言需要用到一个开源库uthash.h¹

C

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

struct hashTable* hashtable;

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

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

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

Python3

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        dct = {}
        n = len(nums)
        for i in range(n):
            tmp = target - nums[i]
            if tmp in dct:
                return [dct[tmp], i]
            dct[nums[i]] = i
        return []

时间复杂度：\(O(N)\) , N 代表数组 nums 的元素个数。
空间复杂度：\(O(N)\) , N 代表创建哈希表的元素个数。

其中Python3脚本也可以稍微简化一下，使用enumerate函数可以对数组添加索引。

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        dct = {}
        for i, num in enumerate(nums):
            if target - num in dct:
                return [dct[target - num], i]
            dct[nums[i]] = i
        return []

实际测试中，以C语言为例，暴力枚举法耗时196ms, 哈希表法耗时8ms，使用哈希表可以大大减少运算时间。

uthash complete example ↩