解决“两数之和”问题:两种实现方法详解

发布于:2025-03-02 ⋅ 阅读:(139) ⋅ 点赞:(0)

目录

 

一、引言

二、暴力枚举法实现

2.1 代码实现

2.2 代码分析

2.3 时间与空间复杂度

三、排序 + 双指针法实现

3.1 代码实现

3.2 代码分析

3.3 时间与空间复杂度

四、总结


 

一、引言

 

在算法学习和编程面试中,“两数之和”是一个经典的问题。它不仅考察对基本数据结构和算法的理解,还能体现程序员解决问题的思路和代码实现能力。给定一个整数数组  nums  和一个整数目标值  target ,要求在数组中找出和为目标值的那两个整数,并返回它们的数组下标,同时规定每种输入只会对应一个答案,且不能使用两次相同的元素。

 

二、暴力枚举法实现

 

2.1 代码实现


 

c

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

    int *result = (int *)malloc(2 * sizeof(int));

    *returnSize = 2;



    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;

                return result;

            }

        }

    }



    return NULL;

}



2.2 代码分析

 

这段代码采用了暴力枚举的方法。外层循环遍历数组中的每个元素,对于每个元素  nums[i] ,内层循环从  i + 1  开始遍历后续的元素  nums[j] ,检查  nums[i] + nums[j]  是否等于目标值  target 。如果找到符合条件的两个数,就将它们的下标存入动态分配的数组  result  中并返回。如果遍历完整个数组都没有找到,则返回  NULL 。

 

2.3 时间与空间复杂度

 

- 时间复杂度:由于使用了两层嵌套循环,时间复杂度为 O(n^2),其中 n 是数组的长度。

 

- 空间复杂度:只使用了常数级别的额外空间,空间复杂度为 O(1)。

 

三、排序 + 双指针法实现

 

3.1 代码实现


 

c

typedef struct {

    int val;

    int index;

} NumIndex;



// 比较函数,用于qsort排序

int cmp(const void *a, const void *b) {

    NumIndex *num1 = (NumIndex *)a;

    NumIndex *num2 = (NumIndex *)b;

    return num1->val - num2->val;

}



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

    // 创建结构体数组,并初始化

    NumIndex *numIndexArr = (NumIndex *)malloc(numsSize * sizeof(NumIndex));

    for (int i = 0; i < numsSize; i++) {

        numIndexArr[i].val = nums[i];

        numIndexArr[i].index = i;

    }



    // 对结构体数组进行排序

    qsort(numIndexArr, numsSize, sizeof(NumIndex), cmp);



    int left = 0, right = numsSize - 1;

    int *result = (int *)malloc(2 * sizeof(int));

    *returnSize = 2;



    while (left < right) {

        int sum = numIndexArr[left].val + numIndexArr[right].val;

        if (sum == target) {

            result[0] = numIndexArr[left].index;

            result[1] = numIndexArr[right].index;

            free(numIndexArr);

            numIndexArr=NULL;

            return result;

        } else if (sum < target) {

            left++;

        } else {

            right--;

        }

    }



    free(numIndexArr);

    free(result);

    numIndexArr=NULL;

    result=NULL;

    return NULL;

}



3.2 代码分析

 

首先定义了一个结构体  NumIndex ,用于存储数组元素的值和其对应的下标。然后创建一个结构体数组  numIndexArr  并初始化,将原数组的元素值和下标存入其中。接着使用  qsort  函数对结构体数组按照元素值进行排序。

 

排序完成后,使用双指针法,左指针  left  指向数组开头,右指针  right  指向数组末尾。通过计算  numIndexArr[left].val + numIndexArr[right].val  的和与目标值  target  比较:


- 如果和等于目标值,说明找到了符合条件的两个数,将它们在原数组中的下标存入  result  数组并返回,同时释放动态分配的  numIndexArr  内存。

 

- 如果和小于目标值,将左指针  left  右移,增大和的值。

 

- 如果和大于目标值,将右指针  right  左移,减小和的值。

如果遍历完整个数组都没有找到符合条件的数,释放所有动态分配的内存并返回  NULL 。


3.3 时间与空间复杂度

 

- 时间复杂度:排序的时间复杂度为 O(n log n),双指针遍历数组的时间复杂度为 O(n),总体时间复杂度为 O(n log n),比暴力枚举法更优。

 

- 空间复杂度:使用了一个额外的结构体数组来存储元素值和下标,空间复杂度为 O(n)。

 

四、总结

 

本文介绍了两种解决“两数之和”问题的方法。暴力枚举法简单直接,但时间复杂度较高;排序 + 双指针法通过对数组进行预处理和双指针的巧妙运用,降低了时间复杂度,提高了算法效率。在实际应用中,可以根据具体的需求和数据规模选择合适的方法。希望通过这篇博客,读者能对该问题有更深入的理解,并且在遇到类似问题时能够灵活运用这些思路和方法。

 


网站公告

今日签到

点亮在社区的每一天
去签到