c++ 面试 【LeetCode】算法：两数之和(twoSum)解法分析

目录

题目 【两数之和】解法一：暴力枚举法1. 时间复杂度分析2. 空间复杂度分析

解法二：哈希表1. 时间复杂度分析2. 空间复杂度分析如果这篇文章对你有所帮助，渴望获得你的一个点赞！

题目 【两数之和】

给定一个整数数组nums和一个整数目标值target，请你在该数组中找出和为目标值target的那两个整数，并返回他们的下标。

示例1：

输入：nums = {2,7,11,15}, target = 9

输出：{0,1}

解释：因为 nums[0] + nums[1] == 9, 返回[0,1]

示例2：

输入：nums = {3,2,4}, target = 6

输出：{1,2}

解法一：暴力枚举法

#include

#include

using namespace std;

//暴力枚举

vector twoSum(vector& nums, int target)

{

int n = nums.size();

for (int i = 0; i < n; ++i)

{

for (int j = i + 1; j < n; ++j)

{

if (nums[i] + nums[j] == target)

{

return { i, j };

}

}

}

return {}; // 如果没有找到满足条件的组合，返回一个空数组

}

void printResult(vector result)

{

if (result.size() > 0)

{

cout << "result elem : {";

for (auto i : result)

{

cout << " " << i << " ";

}

cout << "}" << endl;

}

else

{

cout << "result size : " << result.size() << endl;

}

}

void test01()

{

vector nums = { 2, 7, 11, 15 };

int target = 9;

vector result = twoSum(nums, target);

printResult(result);

}

void test02()

{

vector nums = { 3,2,4 };

int target = 6;

vector result = twoSum(nums, target);

printResult(result);

}

int main()

{

test01();

test02();

return 0;

}

//result

result elem : { 0 1 }

result elem : { 1 2 }

1. 时间复杂度分析

外层循环从索引0遍历到n-1，其中n是数组的长度，因此有n次迭代。内层循环从索引i+1遍历到n-1，最坏情况下需要n-1次迭代。在内层循环中进行了常数时间的加法操作和比较操作。

因此，暴力求解法总体的时间复杂度为O(n^2)，其中n是数组的长度。

2. 空间复杂度分析

除了存储输入数组和输出结果的空间外，该算法没有使用额外的空间。输入数组的空间复杂度为O(n)。输出结果的空间复杂度为O(1)，因为结果是以返回值的形式返回的。

因此，暴力求解法总体的空间复杂度为O(n)。

尽管该方法时间复杂度较高，但对于小规模的问题或输入规模不大的情况下，仍然可以使用。但对于大规模的问题或输入规模较大的情况下，该方法的效率会较低，因此需要考虑使用其他更优化的方法来解决该问题，如哈希表等，来优化时间复杂度。

解法二：哈希表

#include

#include

#include

using namespace std;

vector twoSum(vector& nums, int target)

{

unordered_map numMap;

vector result;

for (int i = 0; i < nums.size(); i++)

{

int complement = target - nums[i];

if (numMap.find(complement) != numMap.end())

{

// 找到了满足条件的两个数

result.push_back(numMap[complement]);

result.push_back(i);

break;

}

// 将当前数及其下标存入哈希表

numMap[nums[i]] = i;

}

return result;

}

void printResult(vector result)

{

if (result.size() > 0)

{

cout << "result elem : {";

for (auto i : result)

{

cout << " " << i << " ";

}

cout << "}" << endl;

}

else

{

cout << "result size : " << result.size() << endl;

}

}

int main()

{

vector nums = { 2, 7, 11, 15 };

int target = 9;

vector result = twoSum(nums, target);

printResult(result);

return 0;

}

//result

result elem : { 0 1 }

该代码使用了哈希表来记录每个数字及其对应的下标。在遍历数组时，对于每个数字，计算出与目标值的差值，然后在哈希表中查找该差值是否已经存在。如果存在，说明找到了两个数的组合，将其下标存入结果数组。如果遍历结束后仍未找到满足条件的两个数，则返回一个空的结果数组。

1. 时间复杂度分析

遍历整个数组需要 O(n) 的时间复杂度，其中 n 是数组的长度。在哈希表中进行查找操作的平均时间复杂度为 O(1)。

因此，哈希表解法总体的时间复杂度为 O(n)。

2. 空间复杂度分析

使用了一个哈希表来存储数组中的元素及其下标，最坏情况下需要存储整个数组的元素，因此空间复杂度为 O(n)。存储结果的数组长度最多为 2，因此额外空间消耗可以忽略不计。

因此，哈希表解法总体的空间复杂度为 O(n)。

需要注意的是，上述分析是基于最坏情况下的复杂度分析，实际运行时的时间和空间消耗会根据输入数据的特征而有所变化。但在平均情况下，哈希表的查找操作具有常数时间复杂度，因此整体的时间复杂度是较低的。

如果这篇文章对你有所帮助，渴望获得你的一个点赞！

推荐文章