Two Sum II

167. 两数之和II

分析

初始化两个指针：
- 左指针 i = 0（指向数组开头）
- 右指针 j = n - 1（指向数组末尾）
双指针移动规则：
- 计算 numbers[i] + numbers[j]：
  - 等于 target → 返回 [i + 1, j + 1]（下标从 1 开始）
  - 大于 target → 右指针左移（减小和）
  - 小于 target → 左指针右移（增大和）
终止条件：
- 当 i >= j 时，搜索结束

时间复杂度

时间复杂度 O(n)

空间复杂度

空间复杂度为 O(1)

C++代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16


class Solution
{
public:
    vector<int> twoSum(vector<int>& numbers, int target)
    {
        for (int i = 0, j = numbers.size() - 1; i < j; ++i)  // 初始化双指针
        {
            while (i < j && numbers[i] + numbers[j] > target) // 如果和大于目标，右指针左移
                -- j;

            if (i < j && numbers[i] + numbers[j] == target)   // 找到目标和
                return {i + 1, j + 1};  // 返回结果（下标从1开始）
        }
        return {};  // 如果没有找到，返回空数组
    }
};