前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >日拱一卒,月进一步(1)

日拱一卒,月进一步(1)

作者头像
用户11039545
发布2024-05-04 08:37:03
540
发布2024-05-04 08:37:03
举报
文章被收录于专栏:c语言c语言

1. 两数之和 - 力扣(LeetCode)

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

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

思路1:暴力求解

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

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

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

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

1 + 2 + 3 + ... + (numsSize - 1)

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

(numsSize * (numsSize - 1)) / 2

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

空间复杂度分析:

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

代码语言:javascript
复制
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:

哈希表(暂时还没有学,所以先开个坑位,以后来填补)

本文参与?腾讯云自媒体分享计划,分享自作者个人站点/博客。
原始发表:2024-05-04,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客?前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与?腾讯云自媒体分享计划? ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
相关产品与服务
对象存储
对象存储(Cloud Object Storage,COS)是由腾讯云推出的无目录层次结构、无数据格式限制,可容纳海量数据且支持 HTTP/HTTPS 协议访问的分布式存储服务。腾讯云 COS 的存储桶空间无容量上限,无需分区管理,适用于 CDN 数据分发、数据万象处理或大数据计算与分析的数据湖等多种场景。
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档


http://www.vxiaotou.com