LeetCode_01两数之和

记录LeefCode历程

题目：两数之和

给定一个整数数组和一个目标值，找出数组中和为目标值的两个数。

假设每个输入只对应一种答案，且相同元素不能被重复利用。

try1

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

报错：

Line 13: control reaches end of non-void function [-Werror=return-type]

分析：程序在运行过程中可能会造成没有进入if语句的情况，从而没有return语句，造成函数没有返回值。

try2

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

执行用时：4ms

如何理解 int *a = (int*)malloc(2*sizeof(int)); 这行代码？

要理解这行代码，我们要先理解等号右边(int*)malloc(2*sizeof(int))这部分，要理解等号右边这部分，就要先理解malloc函数。

malloc 

1.全称memory allocation，中文名是动态内存分配，用于申请一块连续的指定大小的内存块区域以void*类型返回分配的内存区域地址。

2.void* 类型表示未确定类型的指针。C,C++规定，void* 类型可以通过类型转换强制转换为任何其它类型的指针。

这样就清晰了，我们用 sizeof() 函数计算出当下环境中的 int 长度，然后乘以2，我们要这么大的地方，用 malloc 函数进行分配这么大的地方，该函数返回一个 void* 类型的指针，而我们的函数要的是 int* 类型的指针，所以要强制转换为 int* 类型的指针，并用 a 标记它，不然以后去哪里找这块地方。一般而言, malloc() 函数是要配合 free() 函数使用的，考虑注释中解释这里不做考虑。

该题可以延伸：

如果输入不止一个答案呢？

使用哈希表如何处理？