LeetCode经典算法题“两数之和 II – 输入有序数组”考察对数组和指针操作的理解，本文将深入探讨高效解法。
问题描述
给定一个已按升序排序的整数数组，找到两个数使得它们的和等于目标值。返回这两个数的索引 (1-based index)。
约束条件
数组已排序只有一个解不能重复使用同一个元素数组长度 2 ≤ n ≤ 30000数组元素 -1000 ≤ nums[i] ≤ 1000
示例
输入: numbers = [2,7,11,15], target = 9
输出: [1,2]输入: numbers = [2,3,4], target = 6
输出: [1,3]输入: numbers = [-1,0], target = -1
输出: [1,2]
解法：双指针法
由于数组已排序，双指针法是解决此问题的最佳方案，它具有O(n)时间复杂度和O(1)空间复杂度。
算法步骤
初始化指针: leftPointer 指向数组首元素，rightPointer 指向数组尾元素。迭代: 循环执行以下步骤直到 leftPointer 和 rightPointer 相遇：计算 numbers[leftPointer] + numbers[rightPointer] 的和。若和等于目标值，则返回 [leftPointer + 1, rightPointer + 1] (因为索引是1-based)。若和大于目标值，则 rightPointer 左移，减少和。若和小于目标值，则 leftPointer 右移，增加和。
JavaScript 代码实现
/** * @param {number[]} numbers * @param {number} target * @return {number[]} */var twoSum = function(numbers, target) { let left = 0; let right = numbers.length - 1; while (left target) { right--; } else { left++; } }};
登录后复制
算法分析
时间复杂度: O(n)，因为最多遍历数组一次。空间复杂度: O(1)，因为只使用了常数个额外变量。
总结
双指针法巧妙地利用了数组已排序的特性，高效地解决了“两数之和 II – 输入有序数组”问题。 该方法简洁易懂，且时间和空间效率都非常高，是解决此类问题的最佳实践。
以上就是高效求解二和 II – 输入数组已排序的详细内容，更多请关注【创想鸟】其它相关文章！
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容， 请发送邮件至253000106@qq.com举报，一经查实，本站将立刻删除。
发布者：PHP中文网，转转请注明出处：https://www.chuangxiangniao.com/p/2644333.html
