「数据结构与算法」如何快速求两数之和

题目来自于leetcode-cn.com, 描述如下

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

你可以假设每种输入只会对应一个答案。但是，你不能重复利用这个数组中同样的元素。

示例:

给定 nums = [2, 7, 11, 15], target = 9
因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]

最简单的解决方法就是用暴力循环，也就是来两个循环。 原本计划使用Python，发现提交运行的时候超时了，所以只能用C代码实现了。

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

    return NULL;  
}

由于暴力求解法的时间复杂度是 , 最后的运行时间只战胜了一半的人

运行时间

另一种方法，是先用一个循环根据数字和索引建立一个哈希表。之后在对输入数据进行一遍循环，查找当前值被目标值减去后的值，是否在哈希表中。由于哈希表的查找时间是常数，所以总体时间就是 .

代码如下:

#include <stdio.h>
#include <stdlib.h>

int hash(int key, int tableSize)
{   
    unsigned int hashVal = 0;
    hashVal = key << 5 ;
    //printf("%d\n", hashVal);
    return hashVal % tableSize;
}


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

    int i = 0;
    // building hash table
    int tableSize = numsSize * 100  + 3;
    int hashTable[tableSize];
    int key;
    
    for (i = 0; i < tableSize; i ++){
    //printf("%d : %d \n", i, hashTable[i]);  
    hashTable[i] = 0;
    }

    
    for (i = 0; i < numsSize; i++){
        key =  hash(nums[i], tableSize) ;
        hashTable[key] = i + 1;
    }
    
    // find the index
    int *index = (int *)malloc(sizeof(int) * 2);
    for (i = 0; i < numsSize; i++){
        index[0] = i;
        key =  hash(target - nums[i] , tableSize) ;
        if (key < 0 || (hashTable[key] -1) == i){
            continue;
        }

        if (hashTable[key] != 0 ){
            index[1] = hashTable[key] - 1;
            return index;
        }
    }
    return NULL;
    
}

最后的时间显著的提高了。

运行时间

第一个暴力求解法，基本就是直觉，所以写起来很快，也不容易出错。但是第二个利用哈希表的方法，就花了我一个元旦的时间在写代码。

• 一开始，我准备直接用输入数字当做hash的键，然而没想到输入数字有负数。
• 于是我就在代码中加入了判断正负数的操作，正数在原来的基础上加2, 负数转成正数后加1。我以为可以通过了，没想到测试数据里的值特别的大，无法建立那么大的数组。
• 后来，我想到了求余计算，可以不需要那么大数组。于是我非常简单粗暴了的定义了 2*numsSize +3作为除数。然而我被同余定理打败了。
• 经过上面的瞎折腾，我终于放弃蛮干，决定学习点理论。于是我翻开了 「数据结构与算法分析--C语言描述」， 去学习哈希的理论知识。
• 最后我没有用到冲突解决，因为我用了一个比较大的表，后续应该会写的好一点吧。

经过这次折腾，我再一次体会到阅读经典图书的重要性。