给定一个整数数组 nums 和一个整数目标值 target,请你在该数组中找出 和为目标值 target 的那 两个 整数,并返回它们的数组下标。 你可以假设每种输入只会对应一个答案,并且你不能使用两次相同的元素。 你可以按任意顺序返回答案。C++
时间: 2024-10-12 17:03:47 浏览: 27
这个问题描述的是著名的“两数之和”(Two Sum)算法,通常在C++等编程语言中解决。给定一个已排序的整数数组`nums`和一个目标值`target`,你需要找到数组中两个数,使得它们相加等于`target`。这是一个典型的双指针(two-pointer)问题,可以使用两个指针从数组的一端开始向另一端移动:
1. 初始化两个指针,一个指向数组的起始位置(index1 = 0),另一个指向数组的结束位置(index2 = nums.length - 1)。
2. 当两个指针相遇前,比较当前两个指针所指的元素之和与目标值:
a. 如果和大于目标值,说明当前的较大数值太大,将右指针(index2)向左移动一位,减小较大的数。
b. 如果和小于目标值,说明当前的较小数值太小,将左指针(index1)向右移动一位,增大较小的数。
c. 如果和等于目标值,找到了一对符合条件的数,记录它们的下标并跳出循环。
3. 如果遍历结束后仍未找到解,说明不存在这样的两个数。
这个过程的时间复杂度通常是O(n),n是数组的长度,因为它只需要一次遍历。下面是C++的一个简单示例:
```cpp
#include <vector>
using namespace std;
pair<int, int> twoSum(vector<int>& nums, int target) {
int index1 = 0, index2 = nums.size() - 1;
while (index1 < index2) {
int sum = nums[index1] + nums[index2];
if (sum == target) {
return {index1++, index2--}; // 返回两个元素的下标,先增加左指针,再减少右指针
} else if (sum > target) {
index2--;
} else {
index1++;
}
}
// 如果没有找到,返回{-1, -1};
}
```
阅读全文