题目：两数之和
描述：给定一个升序排列的整数数组numbers，从数组中找出两个数满足相加之和等于目标数target。
注意：假设每个输入只对应唯一的答案，而且不可以重复使用相同的元素，返回两数的下标值，以数组形式返回。
前面我们分别使用单个for循环、双重for循环和二分查找算法解决了两数之和的问题。但这些解法都不是最优的，每种算法都有自己的缺陷，要么空间复杂度高，要么时间复杂度高。
时间复杂度对比：双指针算法(O(N)) < 单个for循环(O(N)) < 二分法(O(N * logN)) < 双重for循环(O(N的平方))。
空间复杂度对比：双指针算法(O(1)) = 二分法(O(1)) = 双重for循环(O(1)) < 单个for循环(O(N))。
可以看到，双指针算法无论是时间复杂度还是空间复杂度都是最低的。现在我们就用双指针算法解这道题。
思路：左指针指向数组head，右指针指向数组tail，head+tail > target 则tail 左移，否则head右移
步骤：
1、定义两个指针，左指针left=0, 右指针right=nums.length -1
2、循环遍历
1）如果左右两指针对应元素值之和等于target，就是我们要找的结果，直接return，跳出循环
2）如果左右两指针对应元素之和小于target，只能将left右移，才能把和增加（因为数组元素从左到右越来越大，右移后left变大）
3）如果左右两指针对应元素之和大于target，只能将right左移，才能把和减小（因为数组元素从右往左越来越小，左移后right变小）
时间复杂度：O(N)
空间复杂度：O(1)
package od;
import java.util.Arrays;
/**
* 两数之和（双指针.算法）
* 给定一个升序排列的整数数组numbers，从数组中找出两个数满足相加之和等于目标数target。
* 假设每个输入只对应唯一的答案，而且不可以重复使用相同的元素。
* 返回两数的下标值，以数组形式返回。
* 原文地址：https://www.codernav.com/2829.html
* 更多算法详解：https://www.codernav.com
*/
public class OdTest25 {
public static void main(String[] args) {
// for循环
int[] result = f(new int[]{1, 2, 3, 4, 5, 6}, 10);
System.out.println(Arrays.toString(result));
// while循环
int[] result1 = f1(new int[]{1, 2, 3, 4, 5, 6}, 10);
System.out.println(Arrays.toString(result1));
}
private static int[] f(int[] nums, int target) {
// 左指针
int left = 0;
// 右指针
int right = nums.length - 1;
for (int i = 0; i < nums.length; i++) {
if (nums[left] + nums[right] == target) { // 左右两指针对应元素值之和等于target，就是我们要找的结果
return new int[]{left, right};
} else if (nums[left] + nums[right] < target) { // 左右两指针对应元素之和小于target，只能将left右移，才能把和增加
left++;
} else { // 左右两指针对应元素之和大于target，只能将right左移，才能把和减小
right--;
}
}
return new int[0];
}
private static int[] f1(int[] nums, int target) {
int left = 0;
int right = nums.length - 1;
while (left < right) {
if (nums[left] + nums[right] == target) {
return new int[]{left, right};
} else if (nums[left] + nums[right] < target) {
left++;
} else {
right--;
}
}
return new int[0];
}
}
双指针算法：
双指针算法最核心的用途就是优化时间复杂度，它是一种通过设置两个指针不断进行单向移动来解决问题的算法。在利用双指针算法解题时，考虑原问题如何用暴力算法解出，观察是否可构成单调性，若可以，就可采用双指针算法对暴力算法进行优化。
它包含两种形式：
1、两个指针分别指向不同的序列。比如：归并排序的合并过程。
2、两个指针指向同一个序列。比如：快速排序的划分过程。
一般使用更多，也更难想到的是第2种情况。
双指针算法的核心思想：
双指针算法就是运用单调性使得指针只能单向移动，因此总的时间复杂度只有O(N)，之所以双指针可以实现O(N)的时间复杂度是因为指针只能单向移动，没有指针的回溯，而且每一步都会有指针移动。
暴力算法（双重for循环）和双指针算法有什么区别？
由于双指针具有某种单调性，暴力算法往往能优化为双指针算法。
二者的区别：
1、暴力算法每次在第二层遍历的时候，是会从新开始（j会回溯到初始位置），然后再遍历下去。（假设i是终点，j是起点）
2、双指针算法：由于具有某种单调性，每次在第二层遍历的时候，不需要回溯到初始位置（单调性），而是在满足要求的位置继续走下去或者更新掉。
相关文章
