算法（C）（两数之和）

题目：两数之和
题目描述：给定一个整数数组 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]

示例 3：

输入：nums = [3,3], target = 6
输出：[0,1]

解法一：猫猫直接上暴力枚举法

思路：使用两层for循环，枚举每一个数组中的元素使得将 nums[i] + nums[j] == target 成立的数组下标保存到新开辟的数组ans中，若不成立则返回空数组即可。

/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
int* twoSum(int* nums, int numsSize, int target, int* returnSize){
    for(int i = 0; i < numsSize; i++)
    {
        for(int j = i+1; j < numsSize; j++)
        {
            if(nums[i] + nums[j] == target)
            {
                *returnSize = 2;
                int *ans = (int *)malloc(sizeof(int) * 2); //创建指针数组ans
                ans[0] = i;
                ans[1] = j;
                return ans;
            }
        }
    }
    *returnSize = 0;
    return NULL;
}

解法二：哈希表（想了半小时属实是菜呜呜）

思路：遍历一遍原数组nums，在遍历过程中，将访问过的数 nums[i] 元素以及它的下标 i 存入哈希表中。 原问题 nums[i] + nums[j] == target 转化为：判断 target - nums[i] =>（nums[j]）这个值是否在哈希表中。即每遍历到一个 i，就去判断 target - nums[i] =>（nums[j]）这个值是否在哈希表中。

/**
 * Note: The returned array must be malloced, assume caller calls free().
 */

 #define HashSize 100       //宏定义哈希表大小

 typedef struct Node        //创建哈希结点
 {
     int key;       //关键值
     int index;     //下标
     struct Node *next; //指向下一个的指针结点
 }Node;

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

    Node *H[HashSize];  

    //初始化哈希表
    for(int i = 0; i < HashSize; i++)
    {
        H[i] = (Node *)malloc(sizeof(Node));
        H[i]->key = H[i]->index = -1;
        H[i]->next = NULL;
    }

    //遍历一遍原来的数组
    for(int i = 0; i < numsSize; i++)
    {
        int p = abs(target - nums[i]) % HashSize;   //找到  target - nums[i] 在哈希表对应的的位置
        Node *head = H[p];  //临时结点head
        while(head->next && head->next->key != target - nums[i] )  
        {
            head = head->next;
        }
        if(head->next != NULL)  //能找该位置target - nums[i]这个值的情况（找到符合题意的值）
        {
            *returnSize = 2;
            int *ans = (int *)malloc(sizeof(int) * 2);   //创建临时数组的内存空间
            ans[0] = i;
            ans[1] = head->next->index;
            for(int j = 0; j < HashSize; j++)
            {
                free(H[j]);
            }
            return ans;
        }

        p = abs(nums[i]) % HashSize;   //找到 nums[i] 在哈希表对应的的位置
        head = H[p];
        while(head->next)      //目的是将 nums[i]的值写到哈希表末尾
        {
            head = head->next;
        }
        head->next = (Node *)malloc(sizeof(Node));  //将最后的空指针位置next域创建新的结点
        head->next->key = nums[i];    //写入 nums[i] 的值
        head->next->index = i;        //写入 nums[i] 的下标
        head->next->next = NULL;
    }

    for(int j = 0; j < HashSize; j++)
    {
        free(H[j]);
    }

    *returnSize = 0;
    return NULL;
}

解法三：排序＋二分（猫猫没有想到这种方法，在大神提醒下觉得挺合理的）

思路：可以先对原数组nums进行排序，排序过程中，维护每个值所对应的下标 i 遍历一遍原数组，枚举(i, j)中的 i ，每遍历到一个 i，就通过二分法来寻找符合题意的 j。此方法用到排序还是得用临时数组先存储原数中对应的元素及下标，然后二分法枚举排序后的数组元素，符合条件的数组元素到临时数组取出下标即可。这种方法效率最高，最优解！

static int cmp(const void* a, const void* b) { //qsort()的外部自定义比较函数
    return ((int*)a)[0] - ((int*)b)[0]; //按值从小到大排序
}

int* twoSum(int* nums, int numsSize, int target, int* returnSize) {
    int arr[numsSize][2]; //初始化临时二维数组
    for (int i = 0; i < numsSize; i++) { //将原数组的值以及它对应的下标存入临时二维数组中
        arr[i][0] = nums[i]; //值
        arr[i][1] = i; //该值对应的下标
    }
    qsort(arr, numsSize, sizeof(arr[0]), cmp); //按值排序
    for (int i = 0; i < numsSize; i++) { //遍历一遍原数组
        int left = 0, right = numsSize - 1; //二分区间：[0, numsSize - 1]
        while (left <= right) { //闭区间二分模板
            int mid = (left + right) / 2;
            if (arr[mid][0] == target - nums[i] && i != arr[mid][1]) { //找到符合题意的值
                *returnSize = 2;
                int* ans = (int*)malloc(sizeof(int) * 2);
                ans[0] = i; ans[1] = arr[mid][1]; 
                return ans;
            }
            else if (arr[mid][0] > target - nums[i]) right = mid - 1;
            else left = mid + 1;
        }
    }
    *returnSize = 0;
    return NULL;
}