Day5-两数之和 II - 输入有序数组

🔗 LeetCode 167 - Two Sum II - Input Array Is Sorted

📌 题目描述

给定一个已按升序排列的整数数组 numbers 和一个目标值 target，请你在数组中找出两个数，使得它们的和为目标值 target，并返回这两个数的下标。

注意：

• 返回的答案是一个 1 索引的数组。
• 假设每个输入只对应一个答案，且你不可以重复使用数组中的元素。

---

💡 解题思路

• 由于数组已排序，可以使用双指针法：

  • 初始化两个指针，一个指向数组的开头，一个指向数组的末尾。
  • 如果两指针指向的元素之和等于目标值，返回这两个指针的下标；
  • 如果和小于目标值，说明需要增大和，左指针右移；
  • 如果和大于目标值，说明需要减小和，右指针左移。

• 这种方法时间复杂度是 O(n)，效率较高。

---

✅ JavaScript 实现

var twoSum = function (numbers, target) {
    let left = 0;
    let right = numbers.length - 1;
    
    while (left < right) {
        const sum = numbers[left] + numbers[right];
        if (sum === target) {
            return [left + 1, right + 1];  // 注意返回的下标是从 1 开始的
        } else if (sum < target) {
            left++;
        } else {
            right--;
        }
    }
};

---

🧠 思考拓展

• 如果数组不是有序的，如何解决这个问题？
• 本题和 LeetCode 1. Two Sum 的区别是什么？它是如何利用排序优化解法的？

---