剑指 Offer 57. 和为s的两个数字

大家好，我是吴师兄。

今天继续来学习《剑指Offer》系列的一道经典题目，依旧给出了非常详细的题解和精美的配图与动画。

一、题目描述

输入一个递增排序的数组和一个数字s，在数组中查找两个数，使得它们的和正好是s。如果有多对数字的和等于s，则输出任意一对即可。

示例 1：

输入：nums = [2,7,11,15], target = 9
输出：[2,7] 或者 [7,2]

示例 2：

输入：nums = [10,26,30,31,47,60], target = 40
输出：[10,30] 或者 [30,10]

限制：

• 1 <= nums.length <= 10^5
• 1 <= nums[i] <= 10^6

二、题目解析

为了帮助你更好的理解整个过程，我特意做了一组动画，点开可以查看：

三、参考代码

// 登录 AlgoMooc 官网获取更多算法图解
// https://www.algomooc.com
// 作者：程序员吴师兄
class Solution {
    public int[] twoSum(int[] nums, int target) {

        // 定义头指针 left 
        int left = 0;
 
        // 定义尾指针 right 
        int right = nums.length - 1;


        // 移动 left 和 right ，直到 left 在 right 右侧或者相遇为止
        while(left < right) {

            // 计算此时两个指针指向的元素值之和
            int sum = nums[left] + nums[right];

            // 如果这两个元素值之和小于目标值 target
            if(sum < target){

                // 由于数组是递增排序的数组
                // 所以需要去找更大的数，那 left 向右移动
                left++;

            // 如果这两个元素值之和大于目标值 target
            } else if(sum > target) {
                
                // 由于数组是递增排序的数组
                // 所以需要去找更小的数，那 right 向左移动
                right--;

            // 如果这两个元素值之和等于目标值 target
            } else{

                // 说明找到一对符合要求的数
                // 返回即可
                return new int[] { nums[left], nums[right] };
            } 
        }

        // 否则说明没有找到
        return new int[0];
    }
}