ChunNote
0%

leetCode-167:Two Sum II - Input Array Is Sorted

发表于 分类于

问题描述

给定一个非递减的整数数组，要求在 O(1) 的空间复杂度内找出数组中两个元素和等于目标数字的元素。题目链接：**点我**

样例输入输出

输入：numbers = [2,7,11,15], target = 9

输出：[1, 2]

解释：数组中 2 + 7 = 9，对应数组下标 0 和 1，返回下标加一的值：1 和 2

输入：numbers = [2,3,4], target = 6

输出：[1, 3]

解释：数组中 2 + 4 = 6，对应数组下标 0 和 2，返回下标加一的值：1 和 3

问题解法

此题最简单的做法是用两个 for 循环进行遍历元素判断，但是这样无法利用数组非递减的排序特性。优化的做法是使用双指针，一个在数组开始地方，一个在数组结束地方，如果这两个指针所指元素和大于目标元素，则将右边的指针向左移动，如果这两个指针所指元素和小于目标元素，则将左边的指针向右移动。代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public int[] twoSum(int[] numbers, int target) {
        int left = 0;
        int right = numbers.length - 1;
        while (left < right) {
            if (numbers[left] + numbers[right] == target) {
                break;
            }

            if (numbers[left] + numbers[right] > target) {
                right--;
            } else {
                left++;
            }
        }

        return new int[]{left + 1, right + 1};
    }
}