给定一个整数数组 nums 和一个整数目标值 target,请你在该数组中找出 和为目标值 target 的那 两个 整数,并返回它们的数组下标。 你可以假设每种输入只会对应一个答案。但是,数组中同一个元素在答案里不能重复
时间: 2023-10-20 20:08:26 浏览: 52
你好,给定一个整数数组 nums 和一个整数目标值 target,要找到和为目标值 target 的两个整数并返回它们的数组下标,可以使用哈希表来解决这个问题。我们可以遍历数组,对于每一个元素,计算出需要的另一个数值,如果这个数值已经在哈希表中了,说明找到了两个数的和为目标值,直接返回它们的数组下标即可。如果没有找到,将当前元素的值和下标存入哈希表中,继续遍历后面的元素。以下是代码实现的例子:
```python
class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
index_map = {}
for i in range(len(nums)):
complement = target - nums[i]
if complement in index_map:
return [index_map[complement], i]
index_map[nums[i]] = i
```
其中 index_map 是一个哈希表,用来存储数组中已经出现的元素的值和它们所在的下标。在遍历数组时,首先计算出需要的另一个数值 complement,如果 complement 出现在哈希表中,说明找到了两个数的和为目标值,直接返回它们的数组下标。如果 complement 没有出现在哈希表中,将当前元素的值和下标存入哈希表中,继续遍历后面的元素。
相关问题
给定一个整数数组 nums 和一个整数目标值 target,请你在该数组中找出 和为目标值 target 的那 两个 整数,并返回它们的数组下标。
题目描述:给定一个整数数组 nums 和一个整数目标值 target,请你在该数组中找出和为目标值 target 的那两个整数,并返回它们的数组下标。
解题思路:使用哈希表,遍历数组,将每个元素的值作为键,下标作为值存入哈希表中。在遍历过程中,判断哈希表中是否存在 target - nums[i] 的键,如果存在,则说明找到了两个数的和为 target,返回它们的下标即可。
代码实现:
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
unordered_map<int, int> hash;
for (int i = ; i < nums.size(); i++) {
int complement = target - nums[i];
if (hash.count(complement)) {
return {hash[complement], i};
}
hash[nums[i]] = i;
}
return {};
}
};
jsp写 给定一个整数数组 nums和一个整数目标值 target,请你在该数组中找出和为目标值 target 的那
这个问题可以用暴力枚举、哈希表和双指针等方法解决。其中,哈希表和双指针的时间复杂度都是O(n),而暴力枚举的时间复杂度是O(n^2)。以下是双指针的解法:
首先将数组排序,然后使用双指针i,j分别从数组两端开始向中间靠拢。如果nums[i] + nums[j] > target,则j--;如果nums[i] + nums[j] < target,则i++;如果nums[i] + nums[j] == target,则找到了一组解。
Java代码如下:
```java
public int[] twoSum(int[] nums, int target) {
int[] result = new int[2];
Arrays.sort(nums);
int i = 0, j = nums.length - 1;
while (i < j) {
int sum = nums[i] + nums[j];
if (sum > target) {
j--;
} else if (sum < target) {
i++;
} else {
result[0] = i;
result[1] = j;
break;
}
}
return result;
}
```
相关推荐
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)