首页 > 试题广场 >

两数之和

[编程题]两数之和

热度指数：401430 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

给出一个整型数组 numbers 和一个目标值 target，请在数组中找出两个加起来等于目标值的数的下标，返回的下标按升序排列。

（注：返回的数组下标从1开始算起，保证target一定可以由数组里面2个数字相加得到）

数据范围： $2\leq len(numbers) \leq 10^5$ ， $-10 \leq numbers_i \leq 10^9$ ， $0 \leq target \leq 10^9$

要求：空间复杂度 $O(n)$ ，时间复杂度 $O(nlogn)$

示例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

算法知识视频讲解

查看答案及解析

想去杭州的高级磨洋工在学习

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)

清逍

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)

陈让然

笨办法，时间复杂度高，哈希表不会

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)

整顿职场的牛油果很甜美

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)

牛客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)

帅奶哟。

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)

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(n²)，而散列表法，在无冲突的条件下，理论上时间复杂度为O(n)

发表于 2023-02-16 17:40:32 回复(0)

非科班的小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)

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)

tigerXORkitty

有没有大佬来一个哈希表的算法？

发表于 2022-05-23 01:54:02 回复(2)

和覅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)

4thirteen2one

题目中有说明数据范围：

$2\le len(numbers) \le 10^5$ ，
$-10 \le numbers_i \le 10^9$
$0 \le target \le 10^9$

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

搞不懂你们的答案都加了

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

有什么用……

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

发表于 2022-04-16 14:40:21 回复(2)

一个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)

牛客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)