个人技术分享

原题链接🔗：两数之和
难度等级：简单⭐️

题目

给定一个整数数组 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] 示例 3：

输入：nums = [3,3], target = 6 输出：[0,1]

提示：
2 <= nums.length <= 104
-109 <= nums[i] <= 109
-109 <= target <= 109 只会存在一个有效答案

进阶：你可以想出一个时间复杂度小于 O(n2) 的算法吗？

题解

方法一： 哈希表

1. 解题思路：直接使用c++中unordered_map来完成算法的实现。
2. 复杂度：时间复杂度O(N)，空间复杂度O(N)。
3. 代码流程：

• 定义了一个Solution类，它包含了一个名为twoSum的公共成员函数。
• twoSum函数接收两个参数：一个整数数组nums和一个目标值target。
• 使用一个unordered_map来存储已经遍历过的数字及其对应的索引。
  遍历数组，对于每个元素，我们计算它的补数（target - nums[i]），并检查这个补数是否已经存在于我们的映射中。
• 如果补数存在，说明我们找到了两个数的和等于目标值，我们将这两个索引添加到结果数组中并返回。
• 如果补数不存在，我们将当前元素及其索引添加到映射中，以便后续的查找。 函数返回包含两个索引的数组。

4. c++ demo：

#include <vector>
#include <unordered_map>
#include <iostream>

class Solution {
public:
    std::vector<int> twoSum(std::vector<int>& nums, int target) {
        std::unordered_map<int, int> num_map;
        std::vector<int> result;

        for (int i = 0; i < nums.size(); ++i) {
            int complement = target - nums[i];
            if (num_map.find(complement) != num_map.end()) {
                result.push_back(num_map[complement]);
                result.push_back(i);
                return result;
            }
            num_map[nums[i]] = i;
        }

        return result;
    }
};

int main() {
    Solution solution;
    std::vector<int> nums = { 2, 7, 11, 15 };
    int target = 9;

    std::vector<int> indices = solution.twoSum(nums, target);
    std::cout << "index1: " << indices[0] << ", index2: " << indices[1] << std::endl;
    return 0;
}

输出结果：

index1: 0, index2: 1

方法二：暴力枚举

1. 解题思路：双指针for循环遍历数组中每个数。
2. 复杂度：时间复杂度O(N²)，空间复杂度O(1)。
3. 代码流程：

• Solution类包含一个twoSum函数，它接受一个整数数组nums和一个目标值target。
• 我们首先获取数组的长度n。
• 使用两个嵌套循环遍历数组中的每对元素。外层循环从0到n-1，内层循环从i+1到n，确保我们不会重复检查相同的元素对。
• 在内层循环中，我们检查当前元素对的和是否等于目标值target。
• 如果找到符合条件的元素对，我们返回包含这两个元素索引的数组。
• 如果遍历完所有元素对都没有找到符合条件的对，我们返回一个空数组。

4. c++ demo：

#include <vector>
#include <iostream>

class Solution {
public:
    std::vector<int> twoSum(std::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 std::vector<int>{i, j};
                }
            }
        }
        return std::vector<int>(); // 如果没有找到，返回空数组
    }
};

int main() {
    Solution solution;
    std::vector<int> nums = { 2, 7, 11, 15 };
    int target = 9;
    std::vector<int> indices = solution.twoSum(nums, target);
    if (!indices.empty()) {
        std::cout << "index1: " << indices[0] << ", index2: " << indices[1] << std::endl;
    }
    else {
        std::cout << "No two sum solution found." << std::endl;
    }
    return 0;
}

输出结果：

index1: 0, index2: 1