167. 两数之和 II - 输入有序数组双指针的运用

怼烎@ 2023-02-08 12:49 116阅读 0赞

链接：https://leetcode-cn.com/problems/two-sum-ii-input-array-is-sorted

给定一个已按照 非递减顺序排列 的整数数组 numbers ，请你从数组中找出两个数满足相加之和等于目标数 target 。

函数应该以长度为 2 的整数数组的形式返回这两个数的下标值。numbers 的下标 从 1 开始计数 ，所以答案数组应当满足 1 <= answer\[0\] < answer\[1\] <= numbers.length 。

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

示例 1：

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

示例 2：

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

示例 3：

输入：numbers = [-1,0], target = -1
    输出：[1,2]

提示：

2 <= numbers.length <= 3 \* 10^4  
\-1000 <= numbers\[i\] <= 1000  
**numbers 按 非递减顺序 排列**  
\-1000 <= target <= 1000  
**仅存在一个有效答案**

## 题目分析 ##

LeetCode上两数之和，有两道题：  
第一题 [twoSum][] 简单，就不讲了，各位请看官方题解。  
第二题 [two-sum-ii-input-array-is-sorted][]，是本文讲解的题目，它比第一题多了两个前提，这两个前提，使它可以使用双指针。

它多了哪两个前提呢？

1.  数组按 **非递减顺序** 排列：按字面意思，数组从小到大排列，允许存在相同的元素。而实际给的数组里面，不含重复元素。
2.  仅存在一个有效答案：要么没有，要么有且只有一个。

具备两个前提条件，其实缩小了输入集。**在特定的前提下，就可以使用更精致、定制的优化**。本提就采用双指针。时间复杂度 O(n)。

顺便学习下双指针的运用。

## 代码 ##

class Solution {
        
        public int[] twoSum(int[] numbers, int target) {
        
    
            if (numbers == null || numbers.length == 0) {
        
                return new int[]{
        };
            }
            int length = numbers.length - 1;
            int i = 0;
            int j = numbers.length - 1;
            while (i < j) {
        
                if (numbers[i] + numbers[j] == target) {
        
                    return new int[] {
        i+1, j+1}; // 题目要求下标从1开始，那么数组下标加一即可
                } else if (numbers[i] + numbers[j] < target) {
        
                    i++; // 左指针加一，才有可能等于目标值
                } else {
        
                    j--;
                }
            }
            return new int[]{
        };
        }
    }

![在这里插入图片描述][watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBAa2tra2s3MjEw_size_20_color_FFFFFF_t_70_g_se_x_16]

0ms的写法，是这样的：

class Solution {
        
        public int[] twoSum(int[] numbers, int target) {
        
            int j = numbers.length - 1;
            for (int i = 0; i< numbers.length;i++) {
        
                while (i < j && numbers[i] + numbers[j] > target) j--;
                if (numbers[i] + numbers[j] == target) {
        
                    return new int[]{
        i+1,j+1};
                }
            }
            return new int[]{
        };
        }
    }

仅供参考

本篇完

[twoSum]: https://leetcode-cn.com/problems/two-sum/
[two-sum-ii-input-array-is-sorted]: https://leetcode-cn.com/problems/two-sum-ii-input-array-is-sorted/
[watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBAa2tra2s3MjEw_size_20_color_FFFFFF_t_70_g_se_x_16]: /images/20230208/63890e768b5d4c78880d57654b067366.png