1两数之和

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

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

示例:

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

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

来源：力扣（LeetCode）链接：https://leetcode-cn.com/problems/two-sum 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

Solution 1

Brute Force 暴力解法
思路为遍历数组，将每个元素（设为数组中第i个）与后面剩余的元素（numsSize - i - 1 个）运算，看是否和为target
时间复杂度：O(n2)
空间复杂度：O(1)
执行用时：160 ms
内存消耗：5.9 MB

int *twoSum(int *nums, int numsSize, int target, int *returnSize)
{
    int *returnValue = (int *)malloc(2 * sizeof(int));
    int difference;
    for (int i = 0; i < numsSize; i++)
    {
        // 优化：不直接计算(nums[i] + nums[j] == target)
        // 牺牲空间，记录difference，节省时间
        difference = target - nums[i];
        for (int j = i + 1; j < numsSize; j++)
        {
            if (nums[j] == difference)
            {
                returnValue[0] = i;
                returnValue[1] = j;
            }
        }
    }
    *returnSize = 2;
    return returnValue;
}

Solution 2

quicksort + 双指针
思路为quicksort将数组变为有序，然后双指针夹逼求target
时间复杂度：O(nlogn)
空间复杂度：O(logn)
执行用时：88 ms
内存消耗：6.7 MB

typedef struct _element
{
    int num;
    int index;
} element;

void sort(element *a, int left, int right);
int *twoSum(int *nums, int numsSize, int target, int *returnSize);

int *twoSum(int *nums, int numsSize, int target, int *returnSize)
{
    *returnSize = 2;
    int *returnValue = (int *)malloc(2 * sizeof(int));
    element *e = (element *)malloc(numsSize * sizeof(element));
    for (int i = 0; i < numsSize; i++)
    {
        e[i].num = nums[i];
        e[i].index = i;
    }
    int l = 0;
    int r = numsSize - 1;
    sort(e, l, r);
    int key = target - e[l].num;
    while (l < r)
    {
        while (l < r && key < e[r].num)
            r--;
        if (key == e[r].num)
            break;
        key = target - e[r].num;

        while (l < r && e[l].num < key)
            l++;
        if (key == e[l].num)
            break;
        key = target - e[l].num;
    }
    returnValue[0] = e[l].index;
    returnValue[1] = e[r].index;
    free(e);
    return returnValue;
}

void sort(element *a, int left, int right)
{
    if (left >= right) /*如果左边索引大于或者等于右边的索引就代表已经整理完成一个组了*/
        return;
    int i = left;
    int j = right;
    element key = a[left];

    while (i < j) /*控制在当组内寻找一遍*/
    {
        while (i < j && key.num <= a[j].num)
        /*而寻找结束的条件就是，1，找到一个小于或者大于key的数（大于或小于取决于你想升
        序还是降序）2，没有符合条件1的，并且i与j的大小没有反转*/
        {
            j--; /*向前寻找*/
        }

        a[i] = a[j];
        /*找到一个这样的数后就把它赋给前面的被拿走的i的值（如果第一次循环且key是
        a[left]，那么就是给key）*/

        while (i < j && key.num >= a[i].num)
        /*这是i在当组内向前寻找，同上，不过注意与key的大小关系停止循环和上面相反，
        因为排序思想是把数往两边扔，所以左右两边的数大小与key的关系相反*/
        {
            i++;
        }

        a[j] = a[i];
    }

    a[i] = key;            /*当在当组内找完一遍以后就把中间数key回归*/
    sort(a, left, i - 1);  /*最后用同样的方式对分出来的左边的小组进行同上的做法*/
    sort(a, i + 1, right); /*用同样的方式对分出来的右边的小组进行同上的做法*/
                           /*当然最后可能会出现很多分左右，直到每一组的i = j 为止*/
}

Solution 3

hash table
思路为构建哈希表，存入一个元素的同时，查看当前元素和之前元素是否和为target
时间复杂度：O(n)
空间复杂度：O(n)
执行用时：164 ms
内存消耗：146.3 MB

Attention C 语言的 % 运算，会保留被除数的符号

typedef struct _node
{
    int num;
    int index;
    struct _node *next;
} node;

int *twoSum(int *nums, int numsSize, int target, int *returnSize);

int *twoSum(int *nums, int numsSize, int target, int *returnSize)
{
    int hashTableSize = 2048;
    *returnSize = 2;
    int *returnValue = (int *)malloc(2 * sizeof(int));
    node **hashTable = (node **)malloc(hashTableSize * sizeof(node *));
    node *hashNode = NULL;
    int i, j, dif;
    for (i = 0; i < hashTableSize; i++)
        hashTable[i] = NULL;
    for (i = 0; i < numsSize; i++)
    {
        // hash insert
        hashNode = (node *)malloc(hashTableSize * sizeof(node));
        hashNode->num = nums[i];
        hashNode->index = i;
        // hash function: lambda x: abs(x % hashTableSize)
        hashNode->next = hashTable[abs(nums[i] % hashTableSize)];
        hashTable[abs(nums[i] % hashTableSize)] = hashNode;
        for (j = 0; j < i; j++)
        {
            // hash find
            dif = target - nums[i];
            hashNode = hashTable[abs(dif % hashTableSize)];
            while (hashNode != NULL)
            {
                // hashNode->index != i make sure that won't use self
                if (hashNode->num == dif && hashNode->index != i)
                    goto END_LOOP;
                hashNode = hashNode->next;
            }
        }
    }
END_LOOP:
    returnValue[0] = hashNode->index;
    returnValue[1] = i;
    // free
    for (i = 0; i < hashTableSize; i++)
    {
        while (hashTable[i] != NULL)
        {
            hashNode = hashTable[i];
            hashTable[i] = hashNode->next;
            free(hashNode);
        }
    }
    free(hashTable);
    return returnValue;
}