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

个人主页：手握风云

专栏：算法

一、双指针算法思想

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

二、算法题精讲

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;
    }
}