关于我：微信公众号：面试官问，原创高质量面试题，始于面试题，但不止于面试题。【萌新解题】系列文章试图从新人的角度去看待和解决力扣题目。本题是力扣第 67 题：两数之和 II - 输入有序数组
在上一篇文章 【萌新解题】两数之和 的结尾，我们对原来的无序数组进行排序，然后使用双指针的解法尝试解决两数之和，但最终失败了，而当时的解法用在当前这道题目刚刚好，因为本题输入的是有序数组，因此，不用担心下标被我们重排序后乱掉的问题，当然，上篇文章的解法中，当时我们没有考虑数组排序后，可能存在相同元素的问题，我们挪动过来做简单的修改适配，得到的代码如下：
class Solution { public int[] twoSum(int[] numbers, int target) { // 算出数组长度 int len = numbers.length;
// 左指针指向数组开头，并逐步往中间移动 int left = 0; // 右指针指向数组末尾，并逐步往中间移动 int right = len-1;
// 开始循环 while (left < right) { int sum = numbers[left] + numbers[right]; if (target > sum) { left++; } else if (target < sum) { right--; } else if (target == sum) { // 特别注意，题目中要求数组下标从1开始，前面我们都是按照数组下标是0进行计算 // 因此在返回结果时，下标需要加 1，这里特别容易忽略导致结果错误 return new int[]{left+1, right+1}; } }
return new int[]{-1, -1}; }}
复制代码
这段代码也是本题正确的解法，但如果考虑到由于数组是非递减顺序排列，因此，数组中可能存在连续多个取值相同的元素，因此，在 if 判断中，我们可以选择直接跳过相同的元素，减少外层循环的次数，如下所示：
class Solution { public int[] twoSum(int[] numbers, int target) { // 算出数组长度 int len = numbers.length;
// 左指针指向数组开头，并逐步往中间移动 int left = 0; // 右指针指向数组末尾，并逐步往中间移动 int right = len-1;
// 开始循环 while (left < right) { int sum = numbers[left] + numbers[right]; if (target > sum) { // 当两数之和小于目标值，由于数组已经从小到大排序，因此，左指针要往中间移动 while (numbers[left] == numbers[left+1]) { // 由于数组非递减顺序排列，因此，数组中可能存在连续多个取值相同的元素 // 这里为了避免进行无谓的大循环，选择直接跳过相同的元素 left++; } left++; } else if (target < sum) { // 当两数之和大于目标值时，由于数组已经从小到大排序，因此，右指针要往中间移动 while (numbers[right] == numbers[right-1]) { // 由于数组非递减顺序排列，因此，数组中可能存在连续多个取值相同的元素 // 这里为了避免进行无谓的大循环，选择直接跳过相同的元素 right--; } right--; } else if (target == sum) { // 特别注意，题目中要求数组下标从1开始，前面我们都是按照数组下标是0进行计算 // 因此在返回结果时，下标需要加 1，这里特别容易忽略导致结果错误 return new int[]{left+1, right+1}; } }
return new int[]{-1, -1}; }}
复制代码
可以看到，时间复杂度：O(n)，其中 n 是数组的长度，两个指针移动的总次数最多为 n 次。由于没有使用额外的空间，因此空间复杂度是 O(1)。
评论