有人 LeetCode 第一题都做不出来
大家好，我是吴师兄。
对于很多小伙伴来说，见过的第一道算法题可能是 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 的两个元素。
按照这个逻辑，迅速写出代码：
// 登录 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];
}
}
是不是觉得很简单？
摸鱼时间又掌握了一道算法题！
最后，在这里依旧给自己打个广告，第五期算法训练营已经开营啦！