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

目录

 

一、引言

二、暴力枚举法实现

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)。

 

四、总结

 

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