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