在数组中查找两个数之和等于输入的另一个数
时间: 2023-04-16 14:02:12 浏览: 114
可以使用双指针法或哈希表来解决这个问题。
双指针法:首先将数组排序,然后使用两个指针分别指向数组的头和尾,如果两个指针所指的数之和大于目标数,则将尾指针向左移动;如果两个指针所指的数之和小于目标数,则将头指针向右移动;如果两个指针所指的数之和等于目标数,则找到了符合条件的两个数。
哈希表:遍历数组,将每个数存入哈希表中,然后再遍历数组,对于每个数,计算目标数与该数的差值,然后在哈希表中查找是否存在该差值,如果存在,则找到了符合条件的两个数。
相关问题
用栈和队列的方法在数组中查找两个数之和等于输入的另一个数
我们可以用哈希表来解决这个问题,在遍历数组的同时,将每个数的值和它的下标存入哈希表中,然后对于数组中的每个数,用输入的数减去它的值,得到目标值,然后在哈希表中查找是否存在这样的一个值,如果存在,且这个值不是当前数本身,就说明找到了符合条件的两个数,它们的下标分别是当前数的下标和哈希表中这个值对应的下标。这个算法的时间复杂度是 O(n),空间复杂度是 O(n)。
C++输入一个已经按升序排序过的数组和一个数字,在数组中查找两个数,使得它们的和正好是输入的那个数字
思路:
1. 定义左右指针,分别指向数组的第一个元素和最后一个元素。
2. 当左指针小于右指针时,执行以下循环:
1. 如果左右指针所指元素之和等于目标数字,返回左右指针所指元素的下标。
2. 如果左右指针所指元素之和小于目标数字,将左指针向右移动一位。
3. 如果左右指针所指元素之和大于目标数字,将右指针向左移动一位。
3. 如果数组中不存在符合条件的数,返回-1。
代码实现:
```c
int* findNumbersWithSum(int* nums, int numsSize, int target, int* returnSize){
int left = 0, right = numsSize - 1;
while (left < right) {
int sum = nums[left] + nums[right];
if (sum == target) {
int* result = (int*)malloc(2 * sizeof(int));
result[0] = nums[left];
result[1] = nums[right];
*returnSize = 2;
return result;
} else if (sum < target) {
left++;
} else {
right--;
}
}
*returnSize = 0;
return NULL;
}
```
时间复杂度:$O(n)$
空间复杂度:$O(1)$