首页 > 试题广场 >

两数之和

[编程题]两数之和
  • 热度指数：413055 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
给出一个整型数组 numbers 和一个目标值 target，请在数组中找出两个加起来等于目标值的数的下标，返回的下标按升序排列。
（注：返回的数组下标从1开始算起，保证target一定可以由数组里面2个数字相加得到）

数据范围：，，
要求：空间复杂度 ，时间复杂度
示例1

输入

[3,2,4],6

输出

[2,3]

说明

因为 2+4=6 ，而 2的下标为2 ， 4的下标为3 ，又因为 下标2 < 下标3 ，所以返回[2,3]
示例2

输入

[20,70,110,150],90

输出

[1,2]

说明

20+70=90
算法知识视频讲解
添加回答
C
牛客127938588号头像 牛客127938588号
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param numbers int整型一维数组
* @param numbersLen int numbers数组长度
* @param target int整型
* @return int整型一维数组
* @return int* returnSize 返回数组行数
*/
#include <stdlib.h>
//#include <math.h>

typedef struct{
int key;
int val;
}HashData;

typedef struct{
HashData* Data;
int size;
}HashMap;

HashMap* createHashMap(int size){
HashMap* map = (HashMap*)malloc(sizeof(HashMap));
map->Data = (HashData*)malloc(sizeof(HashData)*size);
map->size = size;
for (int i=0; i<size; i++) {
map->Data[i].key = -1;
map->Data[i].val = -1;
}
return map;
}

int hash(int key, int size){
return abs(key) % size;
}

void insert(HashMap* map, int key, int val){
int index = hash(key, map->size);
while (map->Data[index].key != -1) {
index = (index + 1) % map->size;
}
map->Data[index].key = key;
map->Data[index].val = val;
}

int Search(HashMap* map, int key){
int index = hash(key, map->size);
while(map->Data[index].key != key){
if(map->Data[index].key == -1){
return -1;
}
index = (index + 1) % map->size;
}
return map->Data[index].val;
}

int* twoSum(int* numbers, int numbersLen, int target, int* returnSize ) {
// write code here
*returnSize = 2;
int *ans = calloc(2, sizeof(int));
HashMap* map = createHashMap(numbersLen);
for (int i=0; i<numbersLen; i++) {
int x = Search(map, target - numbers[i]);
if(x != -1){
ans[0] = x + 1;
ans[1] = i + 1;
free(map->Data);
free(map);
return ans;
}
insert(map, numbers[i], i);
}
free(map->Data);
free(map);
return ans;
}
发表于 2025-09-13 00:37:09 回复(0)
C
StellarVibes头像 StellarVibes
int* twoSum(int* numbers, int numbersLen, int target, int* returnSize ) {
    * returnSize=2;
    int* arr=(int*)malloc(sizeof(int)*2);
    for(int i = 0;i<numbersLen;i++)
    {
        if(numbers[i]>target+10) continue;//w为什么要加上面的这行？因为数组中最小的数也就是-10，若数大于目标超过10，则不可能找到另一个数相加=target
        int n = target-numbers[i];
        int m = i+1;
        while(1)
        {
            if(numbers[m]==n)
            {
                arr[0]=i+1;
                arr[1]=m+1;
                return arr;
            }
            m++;
            if(m==numbersLen)
            {
                break;
            }
        }
    }return 0;
}
编辑于 2024-02-23 13:33:54 回复(1)
C
清逍头像 清逍
int* twoSum(int* numbers, int numbersLen, int target, int* returnSize )
{
    for(int i=0;i<numbersLen;i++)
    {
        if(numbers[i]>target)
        {
            continue;
        }
        for(int j=i+1;j<numbersLen;j++)
        {
            if(numbers[j]>target&&numbers[i]>0)
            {
                continue;
            }
            if(numbers[i]+numbers[j]==target)
            {
                int* ret = malloc(sizeof(int)*2);
                ret[0] = i + 1;
                ret[1] = j + 1;
                *returnSize = 2;
                return ret;
            }
        }
    }
    return NULL;
}
编辑于 2024-02-11 23:54:41 回复(2)
C
陈让然头像 陈让然
笨办法，时间复杂度高，哈希表不会
int* twoSum(int* numbers, int numbersLen, int target, int* returnSize ) 
{
    // write code here
    if(!numbers||numbersLen<2)
    {
        return NULL;
    }
    int *arr=(int*)malloc(2*sizeof(int));
    if(!arr)
    {
        return NULL;
    }
    for(int i=0;i<numbersLen;i++)
    {
        if(numbers[i]>target)
        {
            continue;
        }
        for(int j=i+1;j<numbersLen;j++)
        {
            int sum=numbers[i]+numbers[j];
            if(sum==target)
            {
                arr[0]=i+1;
                arr[1]=j+1;
                *returnSize=2;
                return arr;
            }
        }
    }
    free(arr); // 释放内存
    return NULL; // 没有找到符合条件的数对，返回NULL
}


发表于 2023-11-21 09:13:18 回复(0)
C
整顿职场的牛油果很甜美头像 整顿职场的牛油果很甜美 
int* twoSum(int* numbers, int numbersLen, int target, int* returnSize) 
{
    for (int i = 0; i < numbersLen; ++i) 
    {
        for (int j = i + 1; j <numbersLen; ++j) 
        {
            if (numbers[i] + numbers[j] == target) 
            {
                int* ret = malloc(sizeof(int) * 2);
                ret[0] = i+1, ret[1] = j+1;
                *returnSize = 2;
                return ret;
            }
        }
    }
    *returnSize = 0;
    return NULL;
}

发表于 2023-07-15 10:33:31 回复(1)
C
牛客446770844号头像 牛客446770844号 
/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param numbers int整型一维数组 
 * @param numbersLen int numbers数组长度
 * @param target int整型 
 * @return int整型一维数组
 * @return int* returnSize 返回数组行数
 */
int* twoSum(int* numbers, int numbersLen, int target, int* returnSize ) {
    // write code here
    int i,j;
    int *a=(int*)malloc(sizeof(int)*2);//为数组提供空间
    for(i=0;i<numbersLen;i++){
    if(numbers[i]>target+10)//样例中数据>=-10，所以如果数据大于target+10则该数据不可能为目标数据，可以跳过循环
        {
            continue;
        }
        for(j=i+1;j<numbersLen;j++){
            if(numbers[i]+numbers[j]==target){//循环遍历i之后的数据
            a[0]=i+1;//将满足条件的数据下标存入数组
            a[1]=j+1;
            }
        }
    }
    *returnSize=2;
    return a;//返回数组
}

发表于 2023-06-17 18:19:16 回复(0)
C
帅奶哟。头像 帅奶哟。 
static int a[2];

#include <stdlib.h>
int* twoSum(int* numbers, int numbersLen, int target, int* returnSize ) {
    // write code here
    int i, j;
    // int num1, num2;
    // int *s = (int *)malloc(sizeof(int)*2);    //用于返回

    //遍历
    for (i = 0; i < numbersLen; i++){ 

        if (numbers[i] > target+10) {
            continue;
        }

        for (j = i + 1; j < numbersLen; j++){
            if (numbers[i] + numbers[j] == target) {
                a[0] = i+1;
                a[1] = j+1;
            }
        }
    }

    *returnSize = 2;
    return a;
}

发表于 2023-03-17 17:28:51 回复(1)
C
Thruth头像 Thruth
看了下c语言的题解，本来想找一个c语言使用散列表法的来解决的方案，但是最终没找到。
于是自己还是老实地使用传统的散列表法来解决，并给出一个c语言的散列表法以作参考。 
/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param numbers int整型一维数组 
 * @param numbersLen int numbers数组长度
 * @param target int整型 
 * @return int整型一维数组
 * @return int* returnSize 返回数组行数
 */
#include <math.h>
#include <stdio.h>
#include <stdlib.h>
//使用拉链法解决冲突
typedef struct HashMapNode{
    int data;
    struct HashMapNode* next;
}HashMapNode,*HashMapHead;
//这个函数用于给散列表添加元素
void addHashMapNode(HashMapHead* head,int index){
    HashMapHead a = (HashMapHead)malloc(sizeof(HashMapNode));
    a->data=index;
    a->next=NULL;
    if(*head==NULL){
        *head=a;
    }
    else{
        HashMapHead temp = *head;
        HashMapHead b;
        while(temp!=NULL){
            b=temp;
            temp=temp->next;
        }
        a->next=b->next;
        b->next=a;
    }
}
int* twoSum(int* numbers, int numbersLen, int target, int* returnSize ) {
    // write code here
    int* result = (int*)malloc(2*sizeof(int));
    *returnSize+=2;

    //创建一个散列表，大小：50000（主要是想尽量减少冲突的同时，又少用些内存）
    int hashMapLen = 50000;
    HashMapHead hash[hashMapLen];
    //初始化散列表(这一步是挺浪费时间的，但是我真不知道怎么在c语言里初始化一个指针数组为null)
    for(int j=0;j<hashMapLen;j++){
        hash[j]=NULL;
    }

    //work
    for(int i=0;i<numbersLen;i++){
        //注意，求余在计算机语言中是可以出现负数的，因此要进行绝对值处理
        int index=abs((numbers[i])%hashMapLen);
        //下面逻辑思路与官方思路相同
        if(hash[index]!=NULL){
            HashMapHead temp = hash[index];
            while(temp!=NULL){
                if(numbers[temp->data]+numbers[i]==target){
                    result[0] = temp->data+1;
                    result[1] = i+1;
                    return result;
                }
                temp=temp->next;
            }
            int newIndex=abs((target-numbers[i])%hashMapLen);
            addHashMapNode(&hash[newIndex],i);
        }
        else {
            int newIndex=abs((target-numbers[i])%hashMapLen);
            addHashMapNode(&hash[newIndex],i);
        }
    }
    return result;
}
此处给出该方法的效率，并与官方的散列表法作比较，以校验性能没问题。
最终这个解法与官方的c++性能差不多。

最后提一嘴，在c语言的题解中，我发现有很多优化后的双循环能做到更快的速度，不过我想这与测试集的数据有很大关联。不管如何，从理论上来说，即便是优化后的双循环，时间复杂度也还是O(n2)，而散列表法，在无冲突的条件下，理论上时间复杂度为O(n)
发表于 2023-02-16 17:40:32 回复(0)
C
非科班的小fw头像 非科班的小fw 
int* twoSum(int* numbers, int numbersLen, int target, int* returnSize ) {
    // write code here
    int size=2;
    int* target_arr=(int*)malloc(sizeof(int)*size);
    for(int i=0;i<numbersLen;i++)
    {
        if(numbers[i]>target+10)
        {
            continue;
        }
        
        for(int j=i+1;j<numbersLen;j++)
        {  
            if(numbers[i]+numbers[j]==target)
            {
                target_arr[0]=i+1;
                target_arr[1]=j+1;
            }
            
        }
    }
    *returnSize=size;
    return target_arr;

发表于 2022-09-07 09:38:30 回复(0)
C
try～～头像 try～～ 
/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param numbers int整型一维数组 
 * @param numbersLen int numbers数组长度
 * @param target int整型 
 * @return int整型一维数组
 * @return int* returnSize 返回数组行数
 *
 * C语言声明定义全局变量请加上static，防止重复定义
 *
 * C语言声明定义全局变量请加上static，防止重复定义
 */
int* twoSum(int* numbers, int numbersLen, int target, int* returnSize ) {
    // write code here
    int* retarray =(int*)malloc(2*sizeof(int));
    unsigned int cnt1,cnt2,temp;
    for(cnt1 = 0;cnt1<numbersLen-1;cnt1++){
        if(numbers[cnt1]>target){
            continue;
        }
        for(cnt2 = cnt1+1;cnt2<numbersLen;cnt2++){
            if((numbers[cnt1]+numbers[cnt2])==target){
                if(cnt1>cnt2){
                   temp = cnt1;
                   cnt2 = cnt1;
                   cnt1 = temp;
                }
                 retarray[0] = cnt1+1;
                 retarray[1] = cnt2+1; 
                 *returnSize = 2;
            }
        }
    }
    return retarray;
}

发表于 2022-07-29 20:48:03 回复(0)
C
tigerXORkitty头像 tigerXORkitty
有没有大佬来一个哈希表的算法？
发表于 2022-05-23 01:54:02 回复(2)
C
和覅wEJVB头像 和覅wEJVB
int* twoSum(int* numbers, int numbersLen, int target, int* returnSize ) 
{
    int i,j;
    int *arr=(int *)malloc(sizeof(int)*2);
    if(numbersLen==0)
        return NULL;
    *returnSize=2;
    for(i=0;i<numbersLen;i++)
    {
        if(numbers[i]>target)
            continue;
        for(j=i+1;j<numbersLen;j++)
        {
            if(numbers[i]+numbers[j]==target)
            {
                arr[0]=i+1;
                arr[1]=j+1;
                return arr;
            }
        }
    }
    return arr;
    
}
发表于 2022-05-14 15:58:09 回复(0)
C
4thirteen2one头像 4thirteen2one

题目中有说明数据范围：

  • ，

numbers 中是可能存在数为负数的……

搞不懂你们的答案都加了

if(numbers[i]>target) {
    continue;
}

有什么用……

万一 numbers[j] 为负数呢？这时候还能跳过吗？

发表于 2022-04-16 14:40:21 回复(2)
C
一个fw狗头像 一个fw狗 
int* twoSum(int* numbers, int numbersLen, int target, int* returnSize ) {
    // write code here
    int* ret=(int*)malloc(sizeof(int)*2);
     if(numbersLen==0)
        return NULL;
    *returnSize=2;
    int i,j;
    for(i=0;i<numbersLen;i++)
    {
        if(numbers[i]>target)//排除自身已经大于目标的元素
            continue;
        for(j=i+1;j<numbersLen;j++)
        {
            if(numbers[i]+numbers[j]==target)
            {
                ret[0]=i+1;
                ret[1]=j+1;
                return ret;
            }
        }
    }
    return ret;
}

发表于 2022-02-21 17:41:48 回复(0)
C
牛客313433821号头像 牛客313433821号 
int* twoSum(int* numbers, int numbersLen, int target, int* returnSize ) {
    // write code here
    int *result = malloc(8);
    *returnSize = 2;
    for(int i = 0; i < numbersLen; i++)
    {
        // 过滤本身已经超过target的值，可以节省很多时间
        if(numbers[i]>target)
            continue;
        for(int j = i+1;j < numbersLen; j++)
            if(numbers[i]+numbers[j] == target)
            {
                *result = i+1;
                *(result+1) = j+1;
                return result;
            }
    }
    return NULL;
}
没有过滤时间那一步，答案过不了。
发表于 2022-01-26 10:32:12 回复(5)
提交观点

问题信息

数组 哈希
难度：
22条回答 82159浏览

热门推荐

通过挑战的用户

查看代码

相关试题

两数之和

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号