欢迎来到算法小课堂，今天分享的内容是对撞指针在数组中的应用。
分享的题目是LeetCode中的：
接下来，逐一看下如何用对撞指针的思想来解答这三道题目。
01
LeetCode
#167 两数之和||
题目描述：
给定一个已按照
升序排列
的有序数组，找到两个数使得它们相加之和等于目标数。
函数应该返回这两个下标值 index1 和 index2，其中 index1 必须小于 index2。
返回的下标值（index1 和 index2）不是从零开始的。
你可以假设每个输入只对应唯一的答案，而且你不可以重复使用相同的元素。
输入:
numbers = [2, 7, 11, 15], target = 9
解释:
2 与 7 之和等于目标数 9 。因此 index1 = 1, index2 = 2 。
对于该题目可以用暴力解法来解决，使用双重for循环，第一重for循环每次选取一个数，第二重for循环每次从剩余的数中选取一个数，然后计算两数之和，将其值与目标值比较。代码实现如下：
public int[] twoSum(int[] numbers, int target) { int[] res = new int[2]; for(int i = 0; i < numbers.length; i++) { for(int j = i + 1; j < numbers.length; j++) { if (numbers[i] + numbers[j] == target) { res[0] = i+1; res[1] = j+1; } } } return res;}
接着，我们以数组{2,7,11,15}，目标值18来举例说明一下双重for循环这种实现方式的不足之处。
当第一重for循环考察的元素为2时，需要将其和剩余元素7、11、15分别进行求和。但是，剩余元素中最大值是15，其与元素2相加的结果是17，小于目标值18。
也就是说，由于数组是升序排列的，如果可以先计算元素2与元素15的和的话，那么元素2就没有必要与元素15之前的元素7、11再次进行求和计算了。
同样的对于元素15来说，按上述代码实现方式，它需要和元素2、7、11分别进行一次求和计算。但当元素15与元素7进行求和计算时，其和为22，已经大于目标值18。
又由于数组是升序排列的，那么元素7之后的元素11就没有必要与元素15进行求和计算了，因为其和必然大于目标值18。
通过上述分析，由于题目中给定的是一个按照升序排列的数组，我们可以初步得出一个结论，那就是对于该题目来说：
并不是数组中的每个数都需要和剩余的数逐一进行求和计算。
那么怎么避免这种情况呢？接下来看下如何用对撞指针的思路来优化上述实现方式。
我们还是以数组
numbers = [2, 7, 11, 15], target = 18
为例进行讲解。
首先，定义左侧指针left指向数组中第一个元素，右侧指针right指向数组中最后一个元素。
此时，numbers[left]+numbers[right]=17小于target=18。
因为数组是升序排列的，为了让两个数的和
变大
一些，应将左侧指针left向右移动一位，也就是元素2没有必要在与剩余的未考察元素7、11进行求和计算了。
此时，numbers[left]+numbers[right]=22大于target=18。
同样，由于数组是升序排列的，为了让两个数的和
变小
一些，应将右侧指针向左移动一位。同样的，右侧指针向左移动一位，表示元素15没有必要与剩余的未考察元素15进行求和计算了。
此时，numbers[left]+numbers[right]=18等于target=18。因此，找到了两个数7和11，其和等于目标值。
public int[] twoSum(int[] numbers, int target) { int[] res = new int[2];
int left = 0;
int right = numbers.length - 1;
while (left < right) { if (numbers[left] + numbers[right] == target) { res[0] = left + 1; res[1] = right + 1; return res; }else if (numbers[left] + numbers[right] < target) { left++; }else if (numbers[left] + numbers[right] > target) { right--; } }
return res;}
给定一个字符串，验证它是否是回文串，只考虑字母和数字字符，可以忽略字母的大小写。
回文串是一种从左到右读和从右到左读都一样的字符串。题目中描述的回文串是忽略字母大小写并且只考虑字母和数字字符。
接下来以字符串"@CaTnAc#"为例来看一下如何用对撞指针的方法判断一个字符串是否是回文串。
因为题目描述中是忽略字符串大小写的，因此先将字符串中所有字符转为小写字母。
然后，分别定义左指针left，指向字符串左边第一个元素；右指针right指向字符串右边第一个元素。
先看左指针left，当前指向的元素是”@“字符，不是字母也不是数字。因此，left需要向右移动一位。同理，指针right也应向左移动一位。
这时指针left指向的字符”c“与指针right指向的字符”c“是一样的。
因此指针left向右继续移动一位，指针right向左继续移动一位，考察下一对字符。
同理，这时指针left指向的字符”a“与指针right指向的字符”a“是一样的。
因此指针left向右继续移动一位，指针right向左继续移动一位，考察下一对字符。
这时，指针left指向的字符”t“与right指向的字符”n“是不同的，也就是说字符串"@CaTnAc#"不是回文串。
至此，即使有剩余的字符也就不需要考虑了。
通过上述分析，不论左指针left还是右指针right，其向前移动的情况有两种：
-
-
二是当前指针left与指针right指向的字符相同
最后如果指针left与指针right指向的字符不同，则该字符串不是回文串。当指针left指向的位置大于指针right指向的位置时，说明所有字符考察完毕，则所考察的字符串是回文串。代码实现如下:
public boolean isPalindrome(String s) { String lowerCase = s.toLowerCase();
int left = 0; int right = lowerCase.length() - 1; while (left < right) { while (left < right && !Character.isLetterOrDigit(lowerCase.charAt(left))) { left++; }
while (left < right && !Character.isLetterOrDigit(lowerCase.charAt(right))) { right--; }
if (lowerCase.charAt(left) != lowerCase.charAt(right)) { return false; }
left++; right--; }
return true;}
给你 n 个非负整数 a1，a2，...，an，每个数代表坐标中的一个点 (i, ai) 。在坐标内画 n 条垂直线，垂直线 i 的两个端点分别为 (i, ai) 和 (i, 0) 。找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。
