算法日记-LeetCode-167.两数之和

2023-07-08

字数统计: 298字 | 阅读时长≈ 1分

算法日记-LeetCode-167.两数之和

原题链接：167. 两数之和 II - 输入有序数组 - 力扣（LeetCode）

题目大意

给出一个有序非递减数组numbers以及一个目标值target，要求求出数组中和为target的两个数字的下标

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

示例：

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

解题思路

给出数组为有序数组，且非递减，即numbers[i] <= numbers[i+ 1]，且题目中给出了答案唯一的限制

采用双指针的方法，left和right分别指向数组的左右两端，得到的和sum 与target进行比较，如果sum > target，则右侧指针向左移动；反之左侧指针向右移动。

代码

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

本文作者： Naskete
本文链接： https://Naskete.github.io/2023/07/08/algorithm/算法日记-LeetCode-167.两数之和II/
版权声明： 本博客所有文章除特别声明外，均采用 MIT 许可协议。转载请注明出处！