有人 LeetCode 第一题都做不出来！

将 脚本之家 设为“星标⭐”
第一时间收到文章更新

来源公众号：吴师兄学算法  ID：CXYxiaowu

已获得原公众号的授权转载

假期过去一半了，不知道大家是卷着学习了几天，还是玩了几天。

有的同学卷了几天 LeetCode 。

有的同学看了几天比赛，昨天晚上亚运会 DOTA2 的决赛决胜局看的我也是血脉喷张。

今天开始慢慢找回工作的节奏了，先分享一道超级简单的算法题吧。

对于很多小伙伴来说，见过的第一道算法题可能是 LeetCode 上的 1 号问题：两数之和。

这题对于新手、小白来说，难度还是有点，甚至可以说有些残忍，有江湖传言：有人相爱，有人夜里开车看海，有人 LeetCode 第一题都做不出来。

如果你曾经因为这道题目在夜里辗转反侧，那么来看看它的降维版本，缓解缓解压力。

它的降维版本就是剑指 Offer 57. 和为 s 的两个数字。

来看看描述：

输入一个递增排序的数组和一个数字 target，在数组中查找两个数，使得它们的和正好是 target 。

如果有多对数字的和等于 target ，则输出任意一对即可。

比如，输入 nums = [2,7,11,15], target = 9。

输出为 [2,7] 或者 [7,2]。

这题比两数之和额外增加了一个条件，数组是递增有序的，这就极大的降低了求解难度。

既然需要找出两个数，使得它们的和等于 target，那么一开始我就先去随便找两个数。

那随便找哪两个数呢？

一头和一尾。

图片

如果发现两数相加之和大于了目标值，应该怎么做？

让这两个数之和减小呗！

如果发现两数相加之和小于了目标值，应该怎么做？

让这两个数之和增大呗！

于是，就有了如下的操作：

• 设置两个指针，左指针指向数组头部，右指针指向数组尾部。
• 计算两个指针指向的元素之和。
• 如果计算结果之和大于 target ，由于整个数组是递增有序的，所以左边的元素会小于右边的元素，因此让右指针向左边移动可以减小两数之和，靠近 target。

图片

• 如果计算结果之和小于 target ，由于整个数组是递增有序的，所以右边的元素会大于左边的元素，因此让左指针向右边移动可以增大两数之和，靠近 target。
• 如果计算结果之和等于 target ，那么说明找到结果了。

图片

• 如果最后，左右指针相遇，指向同一个元素，说明找不到等于 target 的两个元素。

按照这个逻辑，迅速写出代码：

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];
    }
}

是不是觉得很简单？

摸鱼时间又掌握了一道算法题！

  推荐阅读：