题解 | 两数之和

1、解题思路

1. 哈希表法：使用哈希表存储每个数字及其对应的下标。遍历数组，对于每个数字 num，检查 target - num 是否存在于哈希表中。如果存在，返回这两个数的下标。时间复杂度：O(n)，空间复杂度：O(n)。
2. 排序与双指针法：先将数组排序，然后使用双指针从两端向中间遍历。如果两数之和等于 target，返回它们的下标。如果两数之和小于 target，移动左指针。如果两数之和大于 target，移动右指针。时间复杂度：O(nlogn)（排序），空间复杂度：O(n)（存储原始下标）。
3. 暴力法：双重循环遍历所有可能的数对，检查其和是否等于 target。时间复杂度：O(n^2)，空间复杂度：O(1)。不推荐，因为时间复杂度较高。

2、代码实现

C++

#include <unordered_map>
class Solution {
  public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param numbers int整型vector
     * @param target int整型
     * @return int整型vector
     */
    vector<int> twoSum(vector<int>& numbers, int target) {
        // write code here
        unordered_map<int, int> numToIndex;
        for (int i = 0; i < numbers.size(); ++i) {
            int complement = target - numbers[i];
            if (numToIndex.find(complement) != numToIndex.end()) {
                return {numToIndex[complement] + 1, i + 1};
            }
            numToIndex[numbers[i]] = i;
        }
        return {};
    }
};

Java

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param numbers int整型一维数组 
     * @param target int整型 
     * @return int整型一维数组
     */
    public int[] twoSum (int[] numbers, int target) {
        // write code here
        Map<Integer, Integer> numToIndex = new HashMap<>();
        for (int i = 0; i < numbers.length; i++) {
            int complement = target - numbers[i];
            if (numToIndex.containsKey(complement)) {
                return new int[]{numToIndex.get(complement) + 1, i + 1};
            }
            numToIndex.put(numbers[i], i);
        }
        return new int[0];
    }
}

Python

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param numbers int整型一维数组 
# @param target int整型 
# @return int整型一维数组
#
class Solution:
    def twoSum(self , numbers: List[int], target: int) -> List[int]:
        # write code here
        num_to_index = {}
        for i, num in enumerate(numbers):
            complement = target - num
            if complement in num_to_index:
                return [num_to_index[complement] + 1, i + 1]
            num_to_index[num] = i
        return []

3、复杂度分析

1. 哈希表法： 遍历数组时，将每个数字及其下标存入哈希表。对于每个数字 num，检查 target - num 是否已在哈希表中。如果找到，立即返回两个下标（注意下标从1开始）。
2. 效率： 哈希表法的时间复杂度为 O(n)，因为哈希表的插入和查找操作平均为 O(1)。空间复杂度为 O(n)，因为需要存储数组元素及其下标。
3. 边界条件： 题目保证一定有解，因此不需要处理无解的情况。返回的下标按升序排列，因此无需额外排序。
4. 适用性： 哈希表法适用于大多数情况，尤其是数组较大时。如果数组已排序，可以使用双指针法进一步优化空间复杂度。