167.寻找相加和-双指针(易)

题目要求:

链接:https://leetcode-cn.com/problems/two-sum-ii-input-array-is-sorted/
给定一个已经升序排列的纯数字数组, 找到两个下标(index1<index2),使得它们的相加等于目标target.
输入: numbers = [2, 7, 11, 15], target = 9
输出: [1,2]
解释: 2 与 7 之和等于目标数 9 。因此 index1 = 1, index2 = 2 。

解题思路:

由于题目给定的数组是有序的, 我们可以使用双指针法, 进行范围压缩.
比如: 1,2,5,8,9 target=7
i=0,j=4(下标), 每一步如下:

• 最小值(i)1+最大值(j)9=10 > 目标值7
  需要减小和, 因为i已经是最小, 故减小最大值j, j--.
• 最小值(i)1+最大值(j)8=9 > 目标值7, j--
• 最小值(i)1+最大值(j)5=6 < 目标值7
  需要增大和, 因为j已经最大, 只能增大最小值i, i++
• 最小值(i)2+最大值(j)5=6 == 目标值7, 找到, 返回

注意下标从1开始, 需要返回new int.

时间复杂度分析:

• 暴力算法 T: O(n^2), S: O(1)
• 双指针 T: O(n), S: O(1)

代码:

class Solution {
    public int[] twoSum(int[] numbers, int target) {
        int i = 0, j = numbers.length-1;
        while (i < j) {
            // 最小+最大 > 目标, 增小最大
            if (numbers[i]+numbers[j] > target) j--;
            // 最小+最大 > 目标, 增大最小
            else if (numbers[i]+numbers[j] < target) i++;
            //找到目标值, 返回
            else return new int[]{i+1,j+1};
        }
        return new int[]{-1,-1}; //没有找到
    }
}