优选算法的灵动之章：双指针专题（一）

个人主页：手握风云

专栏：算法

一、双指针算法思想

双指针算法主要用于处理数组、链表等线性数据结构中的问题。它通过设置两个指针，在数据结构上进行遍历和操作，从而实现高效解决问题。

二、算法题精讲

2.1. 查找总价格为目标值的两个商品

我们优先想到的是暴力解法：利用两层for循环来检验两个数的和是否为目标值。那么此时的时间复杂度为 $O(n^{2})$ 。

class Solution {public int[] twoSum(int[] price, int target) {int len = price.length;for(int i=0;i<len;i++){for(int j=i+1;j<len;j++){if(price[i]+price[j] == target){return new int[]{price[i],price[j]};}}}return new int[0];}
}

但题目当中给出数组是按照升序排列的，那么我们就可以利用单调性定义左右两个指针来遍历数组。我们先定义一个sum变量，sum的值等于左右指针所指的值之和。然后通过sum与target的比较，如果sum小于target，则左指针向右移动；如果sum大于target，则右指针向左移动；如果sum等于target，则返回两个数。

完整代码实现：

class Solution {public int[] twoSum(int[] price, int target) {int len = price.length;int left = 0,right = len-1;while(left < right){int sum = price[left] + price[right];if(sum < target){left++;} else if (sum > target) {right--;}else{return new int[]{price[left],price[right]};}}return new int[0];}
}

2.2. 盛最多水的容器

首先，我们得明白如何计算容器的体积，容器的底就可以用两个数组的下标相减得到，容器的高根据木桶效应是数组中最小的元素。我们先选左右边界来作为容器，此时我们记容器体积为v1，如果left指针向右移动，则容器的底一定在减小，如果遇到比左边界小的数，那么高就会减小，如果遇到比左边界大的数，那么高不变。所以容器的体积一定是在减小。此时我们就可以把左边界干掉，left向右移动，得到新的容器体积v2，根据上面的逻辑，我们同理可以把右边界干掉。以此类推，直到找出最大的容器体积。

class Solution {public int maxArea(int[] height) {int len = height.length;int left = 0,right = len-1,ret = 0;while(left < right){int v = Math.min(height[left], height[right]) * (right-left);ret = Math.max(ret,v);if(height[left] < height[right]){left++;}else{right--;}}return ret;}
}