日拱一卒，月进一步（1）

1. 两数之和 - 力扣（LeetCode）

to be honest，由于本人的菜菜又菜菜，看到这题是基本没有思路的，也在最近的测试中比较受挫。但是，有句话说得好：做一件事最重要的就是先从差劲开始。不能沉溺于开头的失败，而是要获取正反馈（从一点一滴开始）。

所以我们从这样一道比较简单的题目获取经验。

思路1：暴力求解

比较容易想到的方法就是：先获取一个x，然后再在数组中寻找target-x。但是要注意的是：由于每一个x之前的元素都已经被匹配过，所以只要寻找x后面的元素即可。

有了思路，我们如何完成完整的代码呢？从出思路，到完成代码，这也是一个重要且艰难的环节。

完成这个代码之前，我们先对其进行时间复杂度和空间复杂度的分析。

这段代码使用了两个嵌套的for循环来查找两个数的和是否等于目标值。外层循环从0遍历到numsSize-1，内层循环从0遍历到i-1。对于每个外层循环的迭代，内层循环最多执行i次。因此，总的时间复杂度是：

这是一个等差数列的和，其和为

所以，时间复杂度是O(numsSize^2)。

空间复杂度分析：

在空间复杂度方面，如果函数找到了两个数的和等于目标值，它会使用malloc分配一个大小为2的整数数组来存储这两个数的索引，并返回这个数组。如果没有找到这样的两个数，函数返回NULL。这意味着除了可能的返回值（一个大小为2的数组）之外，函数没有使用任何与输入大小numsSize成比例的额外空间。因此，空间复杂度是O(1)，不考虑动态分配的内存。

int* twoSum(int* nums, int numsSize, int target, int* returnSize) {
    for(int i=0;i<numsSize;i++)//先确定第一个元素
    {
        for(int j=0;j<i;j++)//元素j在元素i后面查找
        {
            if(nums[i]+nums[j]==target)
            {
                int* ret=malloc(sizeof(int)*2);
                //如果找到这两个元素，那么开辟两个数组空间来存放这两个数字
                //因为要返回这两个数组的下标，所以我们开辟的新数组来储存这两个下标的位置
                ret[0]=i,ret[1]=j;
                *returnSize=2;
                return ret;
            }
        }
    }
    *returnSize=0;
    return NULL;
 
}

思路2：

哈希表（暂时还没有学，所以先开个坑位，以后来填补）