有人 LeetCode 第一题都做不出来！
The following article is from 吴师兄学算法 Author 吴师兄
第一时间收到文章更新
已获得原公众号的授权转载
假期过去一半了，不知道大家是卷着学习了几天，还是玩了几天。
有的同学卷了几天 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];
}
}
是不是觉得很简单？
摸鱼时间又掌握了一道算法题！
前段时间面试了一些人，有这些槽点跟大家说说 面试官：try-catch 到底写在循环里面好，还是外面好？大部分人都会答错！ Go 面试题：string 是线程安全的吗？ 我不允许还有校招&社招党连这些HR黑话都听不懂！ 算法面试真题：完美走位