LeetCode第1题: two-sum(C语言）

1、基础方法
思路：双层遍历数组，如果找到目标的target，退出双层循环

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

    int *result = (int *)malloc(2 * sizeof(int));

    bool found = false;

    for(int i = 0; i < numsSize - 1; i++){

        if(!found){

            for(int j = i + 1; j < numsSize; j++){

                if(nums[i] + nums[j] == target){

                    result[0] = i;

                    result[1] = j;

                    found = true;

                    break;

                }

            }           

        }

    }

    if(found){

        *returnSize = 2;

    }

    else{

        *returnSize = 0;

    }

    return result;

}

2、字典方法
思路：
1、首先遍历数组确定nums的最大值max和最小值min；
2、创建字典map数组，用于快速定位目标值在nums数组中的索引 。map数组以数组下标为要找的目标元素，下标对应的值为该下标在nums数组中的下标位置，例如map[3] = 5，即在数组nums中，元素3在nums中的下标为5。数组大小为max - min + 1，目的是为了将max - min + 1 区间所有元素存入map，由于nums并不是从min-max连续的，所以map会有许多为空元素。为了防止map数组初始化的时候数组元素随机赋值，需要用到calloc函数，将map的元素值均初始化为0。
3、遍历nums数组，对于每一个数组元素nums[i]，如果map中存在lookfornum = target - nums[i]，则直接返回，如果不存在，则建立数组元素的地址映射，map[nums[i] - min] = i + 1（其中，索引存为i + 1，而不是存为i本身，原因为当遍历到数组最小值时，即nums[i] - min = 0时，无法区分该索引到底是min在原nums数组中下标就是0，还是因为map数组在calloc 函数初始化的时候为0）。

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

    int i, max, min;

    max = min = nums[0];

    for(i = 0; i < numsSize; i++) {

        if(nums[i] > max) max = nums[i];

        if(nums[i] < min) min = nums[i];

    }

    int *map  = (int *)calloc((max - min + 1), sizeof(int));

    int *result = (int *)malloc(2 * sizeof(int));

    bool found = false;

    for(i = 0; i < numsSize; i++) {

        int lookfornum = target - nums[i];

        if(lookfornum < min || lookfornum > max) continue;

        int dis = lookfornum - min;

        if (map[dis]) {       

            result[0] = i;

            result[1] = map[dis] - 1;

            found = true;

            break;

        }

        else{

            map[nums[i] - min] = i + 1;

        }

    }

    if(found)

        *returnSize = 2;

    else

        *returnSize= 0;

    return result;

}

本系列文章，旨在打造LeetCode题目解题方法，帮助和引导同学们开阔学习算法思路，由于个人能力和精力的局限性，也会参考其他网站的代码和思路，如有侵权，请联系本人删除。

下一题：LeetCode第2题:add-two-numbers(C语言）