1.两数之和

题目描述

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

你可以假设每种输入只会对应一个答案。但是，数组中同一个元素不能使用两遍。

示例 1:

输入：nums = [2,7,11,15], target = 9
输出：[0,1]
解释：nums[0] + nums[1] = 2 + 7 = 9，返回 [0, 1]。

示例 2:

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

示例 3:

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

提示:

• 可以假设每种输入只会对应一个答案。但是，数组中同一个元素不能使用两遍。

解题思路

类比和解题步骤

考虑类比：假设你在一家商店，每件商品都有一个价格，现在你有一个目标金额，需要找到两件商品的价格之和等于目标金额。你可以通过记录每件商品的价格和对应的索引，然后查找是否存在另一件商品的价格与目标金额减去当前商品的价格相等。

1. 初始化哈希表： 创建一个哈希表，用于存储每个数字及其索引的映射关系。
2. 遍历数组： 遍历数组元素，对于每个元素，计算目标值与当前元素的差值。
3. 查找差值： 在哈希表中查找差值，如果存在，则返回当前元素的索引和差值对应的索引。

特殊案例

• 如果输入数组为空，则直接返回空数组或标识没有答案的结果。

C#代码实现

public int[] TwoSum(int[] nums, int target) {
    // 创建一个字典，用来存储数组中的元素和下标
    Dictionary<int, int> numIndexMap = new Dictionary<int, int>();

    // 遍历数组
    for (int i = 0; i < nums.Length; i++) {
        // 计算当前元素和目标值的差值
        int complement = target - nums[i];

        // 如果字典中包含差值，则返回下标
        if (numIndexMap.ContainsKey(complement)) {
            return new int[] { numIndexMap[complement], i };
        }

        // 如果字典中不包含当前元素，则添加到字典中
        if (!numIndexMap.ContainsKey(nums[i])) {
            numIndexMap.Add(nums[i], i);
        }
    }

    // 没有找到答案
    return new int[0];
}

C代码实现

int* TwoSum(int* nums, int numsSize, int target, int* returnSize) {
    // 哈希表，用于存储数字及其索引的映射关系
    int* numIndexMap = (int*)malloc(sizeof(int) * numsSize * 2);

    for (int i = 0; i < numsSize; i++) {
        int complement = target - nums[i];

        // 在哈希表中查找差值
        if (numIndexMap[complement * 2] != 0) {
            int* result = (int*)malloc(sizeof(int) * 2);
            result[0] = numIndexMap[complement * 2] - 1;
            result[1] = i;
            *returnSize = 2;
            return result;
        }

        // 如果差值不存在，将当前数字及其索引存入哈希表
        numIndexMap[nums[i] * 2] = i + 1;
    }

    // 没有找到答案
    *returnSize = 0;
    return NULL;
}

时间复杂度和空间复杂度

• 时间复杂度：O(n)，其中 n 是数组 nums 的长度。遍历数组一次，每次查找哈希表的操作都是 O(1)。
• 空间复杂度：O(n)，其中 n 是数组 nums 的长度。哈希表的空间复杂度取决于数组中不同元素的个数。