给定一个整数数组nums和一个目标值target,请在数组中找到两个数,它们的和等于目标值。假设每个输入都只有一个答案,且同样的元素不能重复使用。 实现函数twoSum(int[] nums, int target),返回一个长度为2的整数数组,数组中包含两个数的下标,使得它们的和等于目标值。
时间: 2023-10-20 09:12:27 浏览: 136
python 实现给你一个整数数组 nums ,数组中的元素 互不相同 。返回该数组所有可能的子集(幂集)
5星 · 资源好评率100%
可以使用哈希表来解决这个问题,首先遍历一遍数组,将每个数字与其下标存储到哈希表中。然后再遍历一遍数组,对于每个数字,检查哈希表中是否存在目标值减去当前数字的值,如果存在,则说明找到了这两个数,返回它们的下标即可。
以下是 Java 代码实现:
```java
public int[] twoSum(int[] nums, int target) {
Map<Integer, Integer> map = new HashMap<>();
for (int i = 0; i < nums.length; i++) {
map.put(nums[i], i);
}
for (int i = 0; i < nums.length; i++) {
int complement = target - nums[i];
if (map.containsKey(complement) && map.get(complement) != i) {
return new int[] {i, map.get(complement)};
}
}
throw new IllegalArgumentException("No two sum solution");
}
```
时间复杂度为 O(n),空间复杂度为 O(n)。
阅读全文