Medium

题目描述

给你一个下标从 1 开始的整数数组 numbers ，该数组已按 非递减顺序排列 ，请你从数组中找出满足相加之和等于目标数 target 的两个数。如果设这两个数分别是 numbers[index1] 和 numbers[index2] ，则 1 <= index1 < index2 <= numbers.length 。

以长度为 2 的整数数组 [index1, index2] 的形式返回这两个整数的下标 index1 和 index2。

你可以假设每个输入 只对应唯一的答案 ，而且你 不可以 重复使用相同的元素。

你所设计的解决方案必须只使用常量级的额外空间。

示例 1：

输入：numbers = [2,7,11,15], target = 9
输出：[1,2]
解释：2 与 7 之和等于目标数 9 。因此 index1 = 1, index2 = 2 。返回 [1, 2] 。

示例 2：

输入：numbers = [2,3,4], target = 6
输出：[1,3]
解释：2 与 4 之和等于目标数 6 。因此 index1 = 1, index2 = 3 。返回 [1, 3] 。

示例 3：

输入：numbers = [-1,0], target = -1
输出：[1,2]
解释：-1 与 0 之和等于目标数 -1 。因此 index1 = 1, index2 = 2 。返回 [1, 2] 。

提示：

  • 2 <= numbers.length <= 3 * 10⁴
  • -1000 <= numbers[i] <= 1000
  • numbers 按 非递减顺序 排列
  • -1000 <= target <= 1000
  • 仅存在一个有效答案

解题思路

解题思路

这道题是经典的两数之和问题的变形，关键在于数组已经排序且要求常量空间复杂度。

方法一：双指针法（推荐）

由于数组已经排序，我们可以使用双指针技巧：

  • 设置左指针 left 指向数组开头，右指针 right 指向数组结尾
  • 计算两个指针指向元素的和：
    • 如果和等于目标值，找到答案
    • 如果和小于目标值，说明需要更大的数，左指针右移
    • 如果和大于目标值，说明需要更小的数，右指针左移

这种方法利用了数组的有序性，每次都能排除一半的搜索空间。

方法二：二分搜索

对于每个元素，用二分搜索查找 target - numbers[i] 是否存在。但这种方法时间复杂度为 O(n log n)，不如双指针法效率高。

方法三：哈希表

虽然可以用哈希表存储值和索引的映射，但会使用 O(n) 的额外空间，不满足题目要求的常量空间。

综合考虑，双指针法是最优解，既满足时间效率又满足空间要求。

代码实现

class Solution {
public:
    vector<int> twoSum(vector<int>& numbers, int target) {
        int left = 0, right = numbers.size() - 1;
        
        while (left < right) {
            int sum = numbers[left] + numbers[right];
            if (sum == target) {
                return {left + 1, right + 1};
            } else if (sum < target) {
                left++;
            } else {
                right--;
            }
        }
        
        return {};
    }
};

class Solution:
    def twoSum(self, numbers: List[int], target: int) -> List[int]:
        left, right = 0, len(numbers) - 1
        
        while left < right:
            current_sum = numbers[left] + numbers[right]
            if current_sum == target:
                return [left + 1, right + 1]
            elif current_sum < target:
                left += 1
            else:
                right -= 1
        
        return []

public class Solution {
    public int[] TwoSum(int[] numbers, int target) {
        int left = 0, right = numbers.Length - 1;
        
        while (left < right) {
            int sum = numbers[left] + numbers[right];
            if (sum == target) {
                return new int[] {left + 1, right + 1};
            } else if (sum < target) {
                left++;
            } else {
                right--;
            }
        }
        
        return new int[0];
    }
}

/**
 * @param {number[]} numbers
 * @param {number} target
 * @return {number[]}
 */
var twoSum = function(numbers, target) {
    let left = 0;
    let right = numbers.length - 1;
    
    while (left < right) {
        let sum = numbers[left] + numbers[right];
        if (sum === target) {
            return [left + 1, right + 1];
        } else if (sum < target) {
            left++;
        } else {
            right--;
        }
    }
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型双指针法二分搜索法
时间复杂度O(n)O(n log n)
空间复杂度O(1)O(1)

相关题目