LeetCode LCR 006. 两数之和 II - 输入有序数组

Categories:

题目描述
思路分析
1. 解法一：双指针（推荐）
2. 解法二：二分查找
相似题目

题目描述

✅ LCR 006. 两数之和 II - 输入有序数组

思路分析

解法一：双指针（推荐）

核心思路：

数组已排序，利用单调性：左指针指向最小值，右指针指向最大值。

若两数之和等于 target，直接返回两个下标（1-indexed）。

若两数之和小于 target，说明当前最小值太小，左指针右移以增大和。

若两数之和大于 target，说明当前最大值太大，右指针左移以减小和。

题目保证恰好有一个解，因此循环必然终止并返回结果。

复杂度分析：

时间复杂度：O(n)，其中 n 表示数组的长度，左右指针各最多移动 n 次。

空间复杂度：O(1)，只使用了常数级别的额外空间。

class Solution {
    public int[] twoSum(int[] numbers, int target) {
        int left = 0;
        int right = numbers.length - 1;
        while (left < right) {
            int sum = numbers[left] + numbers[right];
            // 找到目标，返回 1-indexed 下标
            if (sum == target) {
                return new int[]{left + 1, right + 1};
            }
            // 和偏小，左指针右移增大和
            if (sum < target) {
                left++;
            } else {
                // 和偏大，右指针左移减小和
                right--;
            }
        }
        return new int[]{-1, -1};
    }
}

func twoSum(numbers []int, target int) []int {
    left, right := 0, len(numbers)-1
    for left < right {
        sum := numbers[left] + numbers[right]
        // 找到目标，返回 1-indexed 下标
        if sum == target {
            return []int{left + 1, right + 1}
        }
        // 和偏小，左指针右移增大和
        if sum < target {
            left++
        } else {
            // 和偏大，右指针左移减小和
            right--
        }
    }
    return []int{-1, -1}
}

解法二：二分查找

核心思路：

固定左指针 i，对 i+1 到末尾的子数组用二分查找寻找 target - numbers[i]。

利用数组有序性，每次固定一个数后，通过二分将搜索范围缩小至 O(log n)。

整体遍历所有左指针位置，总时间复杂度为 O(n log n)。

复杂度分析：

时间复杂度：O(n log n)，其中 n 表示数组的长度，外层遍历 O(n)，内层二分 O(log n)。

空间复杂度：O(1)，只使用了常数级别的额外空间。

class Solution {
    public int[] twoSum(int[] numbers, int target) {
        for (int i = 0; i < numbers.length - 1; i++) {
            int need = target - numbers[i];
            // 在 i+1 到末尾的子数组中二分查找 need
            int lo = i + 1;
            int hi = numbers.length - 1;
            while (lo <= hi) {
                int mid = lo + (hi - lo) / 2;
                if (numbers[mid] == need) {
                    return new int[]{i + 1, mid + 1};
                }
                if (numbers[mid] < need) {
                    lo = mid + 1;
                } else {
                    hi = mid - 1;
                }
            }
        }
        return new int[]{-1, -1};
    }
}

func twoSum(numbers []int, target int) []int {
    for i := 0; i < len(numbers)-1; i++ {
        need := target - numbers[i]
        // 在 i+1 到末尾的子数组中二分查找 need
        lo, hi := i+1, len(numbers)-1
        for lo <= hi {
            mid := lo + (hi-lo)/2
            if numbers[mid] == need {
                return []int{i + 1, mid + 1}
            }
            if numbers[mid] < need {
                lo = mid + 1
            } else {
                hi = mid - 1
            }
        }
    }
    return []int{-1, -1}
}

相似题目

题目	难度	考察点
1. 两数之和	简单	哈希表 / 双指针
15. 三数之和	中等	双指针 / 排序
16. 最接近的三数之和	中等	双指针 / 排序
18. 四数之和	中等	双指针 / 排序
11. 盛最多水的容器	中等	双指针 / 贪心
977. 有序数组的平方	简单	双指针 / 有序数组
633. 平方数之和	中等	双指针 / 数学

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2026/15885564