WHCSRL 技术网

【C语言】leetcode刷题001.两数之和(超详细)

两数之和 leetcode-001

题目来源leetcode

如下图所示

image-20211031134426182

右侧给出了题目的基本模板

/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
int* twoSum(int* nums, int numsSize, int target, int* returnSize)
{

}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7

题目要求

做题之前,我们需要梳理出题目的各项要求

算法题目需要我们非常细致,因为一个小要求的未完成,就会导致格式出问题或者结果出问题,无法通过系统的测试

题目要求如下:

  • 在给定数组nums中找出相加为target的两个数字
  • 同一个数字不能重复
  • 假设每一个target只对应一种答案
  • 找到数字后返回元素的下标
  • 不能更改摸板里的代码

这里还有一个容易被忽略的隐藏条件!

  • 相加的两个数字在数组中是连续的

这个条件是观察3个示例得出的,如果没有这个条件,这道题目就需要我们在数组中进行完全搜索!

我做这道题目的时候就卡在了这个地方!


实现步骤

1.模板中四个值的意义

首先我们要弄明白摸板里的4个值分别代表什么东西

int* twoSum(int* nums, int numsSize, int target, int* returnSize)
  • 1
  • int* nums——nums数组( 此形式等同于int nums[] )
  • numsSize——数组元素的个数
  • target——需要求和的结果
  • int* returnSize——返回值的个数(这个不可以省略!)

再来看题目的要求

需要在给定数组中找到相加=target的两个连续的数字

2.在数组中找到两个连续的元素

一般在数组里面查找一个数字,我们都会想到使用for循环

这里需要查找两个相邻的数字,可以使用两个嵌套的for循环以及两个循环变量来实现

int i=0int j=i+1;
  • 1
  • 2

需要注意的是,j比i大了1,为了防止数组越界访问

for循环里面的判断变量也要相应的差1

   for(int i = 0; i < numsSize - 1; i++)
    {
        for(int j = i+1; j < numsSize; j++)
        {
            
        }
    }
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7

3.判断相加是否等于target

在数组中找到元素后,需要判断它们两个相加是否等于target

if(nums[i] + nums[j] == target)
  • 1

4.返回元素下标

当代码成功找到了两个相加等于target的元素后,我们要返回这两个元素的下标

这里就需要一个新的数组来接收这两个下标,这比单纯的使用两个变量更方便

创建这个数组有两种方法

  1. 使用arr[2]来创建
  2. 使用malloc函数来创建

其中方法二,是题目所给提示里的函数,后续将提及

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

代码示例1

注:leetcode的函数题目只需要补全自定义函数,无需写main函数

在示例1里面,使用普通的方式创建result[2]数组

int* twoSum(int* nums, int numsSize, int target,int* returnSize) 
{
    static int result[2] = {0};//static修饰后,return的地址才能被main接收
    for(int i = 0; i < numsSize - 1; i++)
    {
        for(int j = i+1; j < numsSize; j++)
        {
            if(nums[i] + nums[j] == target)
            {
                result[0] = i;
                result[1] = j;
                *returnSize = 2;//这个不能删除
                return result;
            }
        }
    }
    return 0;
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18

因为我们需要在main函数里面使用result数组的值

所以需要用static来修饰这个数组

不用static修饰的话,出了自定义函数后,result数组的内存空间将被释放

即便我们return了这个数组,它也不能被主函数接收


static的作用

  1. 修饰函数
  2. 修饰全局变量
  3. 修饰局部变量

这里使用的是static的第3个作用,将局部变量数组result,变成静态局部变量

即数组result不会在出自定义函数后销毁


*returnSize是什么?

屏幕前的你是否和我有一样的疑惑,此*returnSize在自定义函数里面没有意义

那为什么不能删除?

要知道,这里的*returnSize是题目的模板给我们的

而且题目没有要求我们书写main函数

其实这里的*returnSize在main函数是有变量传过来的

删除后自定义函数里缺少变量来接受传过来的数据,自然会报错

*returnSize = 2;
  • 1

同时,我们需要在if语句中将它定义为2,即为返回值的个数

具体的分析参考这篇博客==> [链接]


代码示例2

说第二种方法前,我们必须先弄明白malloc函数是什么


什么是malloc函数?

在cplusplus网站,我们可以查看到malloc函数的定义

该函数对应的头文件为,即c语言中的<stdlib.h>

image-20211031154520812

它的作用,简单来说就是在内存中开辟对应字节的空间,赋予给一个指针变量

int *pa = malloc(sizeof(int));
  • 1

上面这个语句的意义是,开辟一个int类型(即4个字节)的空间,赋给指针变量*pa

其中的(int)可以换成(4)

也可以在后面乘上一个数(int)*2表示8个字节

本题需要的是存放两个int整形的数组,malloc函数可以这么写

int *num = malloc(sizeof(int)*2);
  • 1

cplusplus图中的定义里有一句话

If the function failed to allocate the requested block of memory, a null pointer is returned.

如果指针分配错误,函数将返回一个NULL,空指针


malloc使用后free释放

在使用完malloc函数后

  • 需要用free函数来释放malloc创建的内存空间
  • 需要将创建的指针变量指向空指针,以防程序错误调用
 free(pa); pa = NULL;
  • 1

这两个函数是配对的

  • 如果申请后不释放,会内存泄露

  • 如果无故释放,那就是什么也没有做

内存泄漏参考这篇博客==>[链接]


以下就是方法2的完整代码

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

为什么本题使用完malloc函数后没有free呢?

原因还是在本题的提示里

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

这个语句的大概意思应该是:假设main函数里面已有一个free函数来释放内存

所以我们不需要自己加上free函数

  • 自己写代码的时候一定别忘了加哦!

总结

虽然这只是leetcode的第一题,网站打上的难度是“简单”

但对于我这个学艺不精的初学者来说,还是费了一番功夫去完成这道题并理解它

本片博客就是我求解这道题的过程,希望对你有帮助

小声吐槽:

csdn太多繁杂的东西了,有的博客代码不贴代码块,有的答案代码都是错的

还有些人就这么一道题的答案都给你上传一个付费文件(无头像无id无简介,上传几千个资源,怀疑是机器人爬虫)

不管怎么样,至少我弄懂这道题啦!

感谢引用的两篇博客的作者,若不是他们,我也弄不明白这道题!

点个👍再走吧,球球了!这对我真的很重要啊!