【刷题】leetcode 1 . 两数之和

简介: 两数之和

两数之和

题目链接

1 思路一 (简单突破)

最简单的思想: 遍历 从头开始逐个遍历。

首先选定 加数1 然后寻找 加数2 ,如果两者之和满足条件 target 。返回相应下标即可!

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

    for(int i = 0;i < n;i++){
    //加数1 从头开始
        for(int j = i + 1;j < n;j++){
        //加数2 从加数1 后一位开始
            if(nums[i]+nums[j] == target){
            //满足条件即可返回对应下标
                int* a = (int*)malloc(2*sizeof(int)) ;
                a[0] = i;
                a[1] = j;
                //返回的数组大小
                *returnSize = 2;
                //返回数组
                return a;
            }
        }
    }
    //如果全不满足 返回NULL
    *returnSize = 0;
    return NULL;
}

提交! 过啦!!!

但是看看运算时间,居然这么慢!确实咱们的算法时间复杂度是O(n^2),不够快速。

才打败了 69% 的用户。我们不能满足当下,让我们思考有没有其他思路。

2 思路二 (进行优化)

  1. 仔细想想,上面的遍历属实比较费时间,那我们如何改进它呢?
  2. 我的想法是从选择数上下手,取消逐个遍历,改用 二分查找
  3. 二分查找的效率比逐个遍历快许多。但是进行二分查找 的前提是 数组有序!
  4. 如果我们进行简单的排序,那数组下标就被打乱了,无法返回正确值。
  5. 所以我们有必要创建一个新数组,而且是二维数组,储存值和对应下标
  6. 然后不断将和与target 比较,进行二分查找,即可。
//qsort 的比较函数 注意我们传的数据类型是 int* 
static int  compare(int* n1 , int* n2){
    return n1[0] - n2[0] ;
 }
int* twoSum(int* nums, int numsSize, int target, int* returnSize) {
    int n = numsSize;
    int arr[n][2]; // 分别储存下标和值大小 保证同时移动
    // 将原数组的值以及它对应的下标存入临时数组中
    for (int i = 0; i < n; i++) { 
        arr[i][0] = nums[i]; // 值
        arr[i][1] = i; // 该值对应的下标
    }

    //排序
    qsort(arr,n,sizeof(arr[0]),compare);

    //二分寻找
    for(int i = 0; i < n;i++){
        int left = 0 ,right = n-1;//区间[0 , n-1]
        while(left <= right){
            int mid = (left + right) / 2;//区间中点
            //检查是否和为target 并且 两数下标不能相同(否则就是同一个数)
            if(arr[mid][0] + nums[i] == target && i != arr[mid][1] )
            {
                *returnSize = 2 ; //两个数
                
                //开辟两个int类型的空间
                int* ret = (int*)malloc(sizeof(int)*2); 
                //记录两个数下标
                ret[0] = i;
                ret[1] = arr[mid][1];
                return ret;
            }
            //如果大于target 则在小区间寻找
            else if(arr[mid][0] + nums[i] > target){
                right = mid-1;
            }
            //如果小于target 则在大区间寻找
            else {
                left = mid + 1;
            }
        }
    }
    //没有找到
    *returnSize = 0;
    return NULL;

}

提交! 过啦!!!!!!!

这下子打败了98%的用户。我们从 120 ms 一下子来到 8 ms。

时间复杂度来到O(nlogn).

简直就是飞机和马车的差距

那么问题来到为什么还有 2% 比我们快????????

我看了大佬们的代码,使用到了哈希表 而我现在还不会!哭了。

o(╥﹏╥)oo(╥﹏╥)o!o(╥﹏╥)oo(╥﹏╥)o!o(╥﹏╥)oo(╥﹏╥)o!

3 思路三 (哈希表 我还不会)

下面给大家看一下大佬的 0 ms 的代码。

#define HashSize 107 // 哈希表大小

typedef struct Node { // 哈希结点
    int value; // 值
    int index; // 下标
    struct Node* next; // 下指针
}Node;

int* twoSum(int* nums, int numsSize, int target, int* returnSize) {
    int n = numsSize; // 数组长度
    Node* hash[HashSize]; // 哈希表
    for (int i = 0; i < HashSize; i++) { // 初始化哈希表
        hash[i] = (Node*)malloc(sizeof(Node));
        hash[i]->value = hash[i]->index = -1;
        hash[i]->next = NULL;
    }
    for (int i = 0; i < n; i++) { // 遍历一遍原数组
        int pos = abs(target - nums[i]) % HashSize; // 找到target - nums[i]在哈希表中对应的位置
        Node* head = hash[pos];
        while (head->next && head->next->value != target - nums[i]) head = head->next; // 找该位置是否有target - nums[i]这个值
        if (head->next) { // 找到符合题意的值
            *returnSize = 2;
            int* ans = (int*)malloc(sizeof(int) * 2);
            ans[0] = i; ans[1] = head->next->index; // 写入答案
            for (int i = 0; i < HashSize; i++) free(hash[i]);
            return ans;
        }
        pos = abs(nums[i]) % HashSize; // 找到nums[i]在哈希表中对应的位置
        head = hash[pos];
        while (head->next) head = head->next; // 写在这个位置的末尾
        head->next = (Node*)malloc(sizeof(Node));
        head->next->value = nums[i]; // 写入该值
        head->next->index = i; // 写入该值对应的下标
        head->next->next = NULL;
    }
    for (int i = 0; i < HashSize; i++) free(hash[i]);
    *returnSize = 0;
    return NULL;
}

C语言的缺陷 , 需要手撕哈希表。

来看大佬 C++ 的代码,真的非常美观!!!!

美!!!! 帅!!!! 炸裂!!!!

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        map<int,int> a;//提供一对一的hash
        vector<int> b(2,-1);//用来承载结果,初始化一个大小为2,值为-1的容器b
        for(int i=0;i<nums.size();i++)
        {
            if(a.count(target-nums[i])>0)
            {
                b[0]=a[target-nums[i]];
                b[1]=i;
                break;
            }
            a[nums[i]]=i;//反过来放入map中,用来获取结果下标
        }
        return b;
    };
};

谢谢阅读Thanks♪(・ω・)ノ

下一篇文章见!!!

相关文章
|
3月前
|
Unix Shell Linux
LeetCode刷题 Shell编程四则 | 194. 转置文件 192. 统计词频 193. 有效电话号码 195. 第十行
本文提供了几个Linux shell脚本编程问题的解决方案,包括转置文件内容、统计词频、验证有效电话号码和提取文件的第十行,每个问题都给出了至少一种实现方法。
LeetCode刷题 Shell编程四则 | 194. 转置文件 192. 统计词频 193. 有效电话号码 195. 第十行
|
4月前
|
搜索推荐 索引 Python
【Leetcode刷题Python】牛客. 数组中未出现的最小正整数
本文介绍了牛客网题目"数组中未出现的最小正整数"的解法,提供了一种满足O(n)时间复杂度和O(1)空间复杂度要求的原地排序算法,并给出了Python实现代码。
119 2
|
29天前
|
机器学习/深度学习 人工智能 自然语言处理
280页PDF,全方位评估OpenAI o1,Leetcode刷题准确率竟这么高
【10月更文挑战第24天】近年来,OpenAI的o1模型在大型语言模型(LLMs)中脱颖而出,展现出卓越的推理能力和知识整合能力。基于Transformer架构,o1模型采用了链式思维和强化学习等先进技术,显著提升了其在编程竞赛、医学影像报告生成、数学问题解决、自然语言推理和芯片设计等领域的表现。本文将全面评估o1模型的性能及其对AI研究和应用的潜在影响。
25 1
|
3月前
|
数据采集 负载均衡 安全
LeetCode刷题 多线程编程九则 | 1188. 设计有限阻塞队列 1242. 多线程网页爬虫 1279. 红绿灯路口
本文提供了多个多线程编程问题的解决方案,包括设计有限阻塞队列、多线程网页爬虫、红绿灯路口等,每个问题都给出了至少一种实现方法,涵盖了互斥锁、条件变量、信号量等线程同步机制的使用。
LeetCode刷题 多线程编程九则 | 1188. 设计有限阻塞队列 1242. 多线程网页爬虫 1279. 红绿灯路口
|
2月前
|
C++
Leetcode第一题(两数之和)
这篇文章介绍了解决LeetCode第一题“两数之和”的两种方法:暴力法和哈希表法,并提供了相应的C++代码实现。
33 0
Leetcode第一题(两数之和)
|
2月前
|
存储 C++ 容器
【LeetCode 13】1.两数之和
【LeetCode 13】1.两数之和
16 0
|
4月前
|
存储 索引
LeetCode------两数之和(3)【数组】
这篇文章介绍了LeetCode上的"两数之和"问题,提供了两种解法:一种是暴力求解法,通过双层循环遍历数组元素对查找两数之和为目标值的索引,时间复杂度为O(n^2);另一种是使用HashMap优化,通过存储元素值和索引,时间复杂度降低到O(n)。
LeetCode------两数之和(3)【数组】
|
4月前
|
Python
【Leetcode刷题Python】50. Pow(x, n)
本文介绍了LeetCode第50题"Pow(x, n)"的解法,题目要求实现计算x的n次幂的函数,文章提供了递归分治法的详细解析和Python实现代码。
28 1
|
4月前
|
算法 Python
【Leetcode刷题Python】73. 矩阵置零
本文介绍了LeetCode第73题的解法,题目要求在给定矩阵中将所有值为0的元素所在的行和列全部置为0,并提供了一种原地算法的Python实现。
32 0
【Leetcode刷题Python】73. 矩阵置零
|
4月前
|
算法
LeetCode第1题两数之和
该文章介绍了 LeetCode 第 1 题两数之和的解法,通过使用 HashMap 来记录数组元素及其下标,以 O(n)的时间复杂度解决问题。