找出数组中和为目标值的两个数
时间: 2023-06-15 11:07:10 浏览: 66
这个问题可以用哈希表来解决,具体步骤如下:
1. 创建一个空的哈希表
2. 遍历数组中的每个数,对于每个数执行以下操作:
- 计算目标值与当前数的差值 diff
- 在哈希表中查找是否存在键为 diff 的项,如果存在,则说明找到了两个数的和为目标值,直接返回这两个数的下标即可
- 如果不存在,则将当前数作为键,下标作为值存入哈希表中
3. 如果遍历完整个数组都没有找到符合条件的两个数,则说明不存在这样的两个数,返回空数组即可
下面是代码实现:
```
def twoSum(nums, target):
hash_dict = {}
for i in range(len(nums)):
diff = target - nums[i]
if diff in hash_dict:
return [hash_dict[diff], i]
else:
hash_dict[nums[i]] = i
return []
```
该算法的时间复杂度为O(n),其中n为数组中元素的个数。
相关问题
找出数组中和为目标值的两个数 找出数组中和为目标值的两个数代码
以下是使用双指针实现的 C++ 源代码,用于在给定数组中查找和为目标值的两个数:
```c++
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
vector<int> twoSum(vector<int>& nums, int target) {
int left = 0;
int right = nums.size() - 1;
while (left < right) {
int sum = nums[left] + nums[right];
if (sum == target) {
return {left, right};
} else if (sum < target) {
left++;
} else {
right--;
}
}
return {};
}
int main() {
vector<int> nums = {2, 7, 11, 15};
int target = 9;
vector<int> result = twoSum(nums, target);
cout << "[" << result[0] << ", " << result[1] << "]" << endl;
return 0;
}
```
该算法的时间复杂度为 O(nlogn),其中 n 是数组的长度,因为需要排序。空间复杂度为 O(1),因为只需要两个指针的额外空间。
用C语言实现找出数组中和为目标值的两个数
可以使用双重循环来实现,依次枚举数组中的每一个数,再在剩余的数中查找是否有与当前数相加等于目标值的数。具体实现可参考以下代码:
```
#include <stdio.h>
void findSum(int arr[], int n, int target) {
int i, j;
for(i = 0; i < n; i++) {
for(j = i + 1; j < n; j++) {
if(arr[i] + arr[j] == target) {
printf("找到两个数,它们的下标分别为 %d 和 %d。\n", i, j);
}
}
}
}
int main() {
int arr[] = {2, 7, 11, 15, 3, 6};
int n = sizeof(arr) / sizeof(arr[0]);
int target = 9;
findSum(arr, n, target);
return 0;
}
```
输出结果:
```
找到两个数,它们的下标分别为 0 和 1。
找到两个数,它们的下标分别为 4 和 5。
```