大家好,我是吴师兄。
假期过去一半了,不知道大家是卷着学习了几天,还是玩了几天。
有的同学卷了几天 LeetCode 。
有的同学看了几天比赛,昨天晚上亚运会 DOTA2 的决赛决胜局看的我也是血脉喷张。
今天开始慢慢找回工作的节奏了,先分享一道超级简单的算法题吧。
对于很多小伙伴来说,见过的第一道算法题可能是 LeetCode 上的 1 号问题:两数之和。
这题对于新手、小白来说,难度还是有点,甚至可以说有些残忍,有江湖传言:有人相爱,有人夜里开车看海,有人 LeetCode 第一题都做不出来。
如果你曾经因为这道题目在夜里辗转反侧,那么来看看它的降维版本,缓解缓解压力。
它的降维版本就是剑指 Offer 57. 和为 s 的两个数字。
来看看描述:
输入一个递增排序的数组和一个数字 target,在数组中查找两个数,使得它们的和正好是 target 。
如果有多对数字的和等于 target ,则输出任意一对即可。
比如,输入 nums = [2,7,11,15], target = 9
。
输出为 [2,7] 或者 [7,2]
。
这题比两数之和额外增加了一个条件,数组是递增有序的,这就极大的降低了求解难度。
既然需要找出两个数,使得它们的和等于 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];
}
}
是不是觉得很简单?