#P4000. 两数组之和
-
ID: 2202
Tried: 533
Accepted: 156
Difficulty: 2
两数组之和
题目内容
给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那两个整数，并输出它们的数组下标。
你可以假设每种输入只会对应一个答案，并且你不能使用两次相同的元素。
你可以按任意顺序输出答案。
输入描述
输入共两行。
-
第一行为两个个整数n，target，代表数组nums的长度和目标值。
-
第二行为n个整数nums0,nums1,...,numsn−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<=104
- −109<=nums[i]<=109
- −109<=target<=109
- 只会存在一个有效答案
两数组之和
题面分析
题目要求在一个整数数组 nums 中找出两个数，使得它们的和等于给定的目标值 target，并返回这两个数的数组下标。题目保证每种输入只会对应一个答案，并且不能使用两次相同的元素。
解题思路
-
暴力枚举法：最直观的方法是使用双重循环，遍历数组中的每一对数，检查它们的和是否等于
target。这种方法的时间复杂度为 O(n2)，在数据量较大时效率较低。 -
哈希表法：为了提高效率，可以使用哈希表（字典）来存储数组中的元素及其对应的下标。遍历数组时，对于每个元素
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;
}