两数组之和

题面分析

题目要求在一个整数数组 nums 中找出两个数，使得它们的和等于给定的目标值 target，并返回这两个数的数组下标。题目保证每种输入只会对应一个答案，并且不能使用两次相同的元素。

解题思路

1. 暴力枚举法：最直观的方法是使用双重循环，遍历数组中的每一对数，检查它们的和是否等于 target。这种方法的时间复杂度为 $O(n^2)$，在数据量较大时效率较低。

2. 哈希表法：为了提高效率，可以使用哈希表（字典）来存储数组中的元素及其对应的下标。遍历数组时，对于每个元素 nums[i]，检查 target - nums[i] 是否在哈希表中。如果存在，则返回这两个数的下标；否则，将当前元素及其下标存入哈希表。这种方法的时间复杂度为 $O(n)$，空间复杂度为 $O(n)$。

复杂度分析

• 时间复杂度：哈希表法的时间复杂度为 $O(n)$，因为只需要遍历数组一次。
• 空间复杂度：哈希表法的空间复杂度为 $O(n)$，因为需要存储数组中的元素及其下标。

代码实现

Python

class Solution:
    def twoSum(self, nums, target) :
        # 创建一个哈希表来存储元素及其下标 
        num_to_index = {}
        # 遍历数组 
        for i, num in enumerate(nums):
            # 计算需要的补数 
            complement = target - num 
            # 如果补数在哈希表中，返回对应的下标 
            if complement in num_to_index:
                return [num_to_index[complement], i]
            # 否则，将当前元素及其下标存入哈希表 
            num_to_index[num] = i 
        # 如果没有找到，返回空列表（根据题目，这种情况不会发生）
        return []
 
# 输入处理 
n, target = map(int, input().split())
nums = list(map(int, input().split()))
 
# 创建 Solution 类的实例并调用 two_sum 方法 
solution = Solution()
result = solution.twoSum(nums,  target)
 
# 输出结果 
print(result[0], result[1])

Java

import java.io.*; 
import java.util.HashMap; 
import java.util.StringTokenizer; 
 
public class Main {
    
    public class Solution {
        public int[] twoSum(int[] nums, int target) {
            // 创建一个哈希表来存储元素及其下标 
            HashMap<Integer, Integer> numToIndex = new HashMap<>();
            // 遍历数组 
            for (int i = 0; i < nums.length;  i++) {
                // 计算需要的补数 
                int complement = target - nums[i];
                // 如果补数在哈希表中，返回对应的下标 
                if (numToIndex.containsKey(complement))  {
                    return new int[]{numToIndex.get(complement),  i};
                }
                // 否则，将当前元素及其下标存入哈希表 
                numToIndex.put(nums[i],  i);
            }
            // 如果没有找到，返回空数组（根据题目，这种情况不会发生）
            return new int[0];
        }
    }
 
    public static void main(String[] args) throws IOException {
        // 使用 BufferedReader 和 StringTokenizer 高效读取输入 
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); 
        StringTokenizer st = new StringTokenizer(br.readLine()); 
 
        // 读取数组长度 n 和目标值 target 
        int n = Integer.parseInt(st.nextToken()); 
        int target = Integer.parseInt(st.nextToken()); 
 
        // 读取数组 nums 
        int[] nums = new int[n];
        st = new StringTokenizer(br.readLine()); 
        for (int i = 0; i < n; i++) {
            nums[i] = Integer.parseInt(st.nextToken()); 
        }
 
        // 创建 Main 对象以访问非静态的 Solution 类 
        Main main = new Main();
        Solution solution = main.new  Solution();
        int[] result = solution.twoSum(nums,  target);
 
        // 输出结果 
        System.out.println(result[0]  + " " + result[1]);
    }
} 

C++

#include <iostream>
#include <unordered_map>
#include <vector>
 
using namespace std;
 
class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        // 创建一个哈希表来存储元素及其下标 
        unordered_map<int, int> numToIndex;
        // 遍历数组 
        for (int i = 0; i < (int)nums.size();  i++) {
            // 计算需要的补数 
            int complement = target - nums[i];
            // 如果补数在哈希表中，返回对应的下标 
            if (numToIndex.find(complement)  != numToIndex.end())  {
                return {numToIndex[complement], i};
            }
            // 否则，将当前元素及其下标存入哈希表 
            numToIndex[nums[i]] = i;
        }
        // 如果没有找到，返回空向量（根据题目，这种情况不会发生）
        return {};
    }
};
 
int main() {
    // 读取输入 
    int n, target;
    cin >> n >> target;
    vector<int> nums(n);
    for (int i = 0; i < n; i++) {
        cin >> nums[i];
    }
 
    // 创建 Solution 对象并调用 twoSum 方法 
    Solution solution;
    vector<int> result = solution.twoSum(nums,  target);
 
    // 输出结果 
    cout << result[0] << " " << result[1] << endl;
 
    return 0;
}

LeetCode 1. 两数之和-原题链接

题目内容

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

你可以假设每种输入只会对应一个答案，并且你不能使用两次相同的元素。

你可以按任意顺序输出答案。

输入描述

输入共两行。

• 第一行为两个个整数$n，target$，代表数组$nums$的长度和目标值。

• 第二行为$n$个整数$nums_0,nums_1,...,nums_{n-1}$，数字之间以空格分隔。

输出描述

一行两个整数，以空格分隔，表示两个元素的数组下标。

样例1

输入

4 9
2 7 11 15

输出

0 1

说明

因为 $nums[0] + nums[1] == 9$ ，输出$0, 1$

样例2

输入

3 6
3 2 4

输出

1 2

提示

• $2 <= nums.length <= 10^4$
• $-10^9 <= nums[i] <= 10^9$
• $-10^9 <= target <= 10^9$
• 只会存在一个有效答案