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

一、题目描述

输入一个递增排序的数组和一个数字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];
    }
}

2、C++ 代码

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        // 定义头指针 left 
        int left = 0;

        // 定义尾指针 right 
        int right = nums.size() - 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 vector<int>{nums[left], nums[right]};
            } 
        }

        // 否则说明没有找到
        return vector<int>{0, 0};
    }
};

3、Python 代码

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

        # 定义头指针 left 
        left = 0 

        # 定义尾指针 right 
        right = len(nums) - 1 


        # 移动 left 和 right ，直到 left 在 right 右侧或者相遇为止
        while left < right : 

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

            # 如果这两个元素值之和小于目标值 target
            if sum < target : 

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

            # 如果这两个元素值之和大于目标值 target
            elif sum > target : 

                # 由于数组是递增排序的数组
                # 所以需要去找更小的数，那 right 向左移动
                right -= 1 

            # 如果这两个元素值之和等于目标值 target
            else : 

                # 说明找到一对符合要求的数
                # 返回即可
                return nums[left], nums[right] 



        # 否则说明没有找到
        return []

程序员吴师兄算法训练营永久会员

收藏 海报 链接