前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >血脉喷张​,有人 LeetCode 第一题都做不出来!

血脉喷张​,有人 LeetCode 第一题都做不出来!

作者头像
五分钟学算法
发布2023-10-04 14:04:47
2280
发布2023-10-04 14:04:47
举报
文章被收录于专栏:五分钟学算法

大家好,我是吴师兄。

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

有的同学卷了几天 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 的两个元素。

按照这个逻辑,迅速写出代码:

代码语言:javascript
复制
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];
    }
}

是不是觉得很简单?

本文参与 腾讯云自媒体同步曝光计划,分享自微信公众号。
原始发表:2023-10-03 20:00,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 五分钟学算法 微信公众号,前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档