题目 【两数之和】

给定一个整数数组

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 <iostream>
#include <vector>
using namespace std;

//暴力枚举
vector<int> twoSum(vector<int>& 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<int> 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<int> nums = { 2, 7, 11, 15 };
    int target = 9;

    vector<int> result = twoSum(nums, target);
    printResult(result);
}

void test02()
{
    vector<int> nums = { 3,2,4 };
    int target = 6;

    vector<int> 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 <iostream>
#include <unordered_map>
#include <vector>
using namespace std;

vector<int> twoSum(vector<int>& nums, int target) 
{
    unordered_map<int, int> numMap;
    vector<int> 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<int> 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<int> nums = { 2, 7, 11, 15 };
    int target = 9;

    vector<int> 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)


。

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

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