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

个人主页：手握风云

专栏：算法

一、双指针算法思想

二、算法题精讲

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

2.2. 盛最多水的容器

编辑

2.3. 移动零

2.4. 有效的三角形个数

一、双指针算法思想

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

二、算法题精讲

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

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

java">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，则返回两个数。

完整代码实现：

java">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，根据上面的逻辑，我们同理可以把右边界干掉。以此类推，直到找出最大的容器体积。

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

2.3. 移动零

本题要求在不复制数组的情况下原地对数组进行操作。我们先定义cur和dest两个指针，cur指针的作用是先扫描数组，将数组分为已处理和待处理的两个区间，dest指针是将已处理的区间变为非零区间和零区间。当cur遇到零元素时，不做任何处理，直接让cur向右移动一位；当cur遇到非零元素时，先让dest向右移动一位，再让两个指针所指向的值进行交换。直到cur遍历完整个数组

完整代码实现：

java">public class Solution {
    public void moveZeroes(int[] nums){
        for (int cur = 0,dest = -1; cur < nums.length; cur++) {
            if(nums[cur] != 0){
                dest++;
                int temp = nums[cur];
                nums[cur] = nums[dest];
                nums[dest] = temp;
            }
        }
    }
}

2.4. 有效的三角形个数

要找到有效的三角形个数，就是在数组中找到能够构成三角形的三元子数组。我们首先想到的暴力解法，利用三层for循环来查找，此时的时间复杂度为 $O(n^{3})$ 。

对于三条边的比较，我们只需要让三角形较小的两条边之和与最大的边进行比较即可。，要想得到最大值，首先我们可以先对数组进行一个排序，使数组呈升序排列。排序之后，先固定右侧的最大值，在定义left和right两个指针，让right指针指向被固定值的左侧。如果两个元素之和大于最大值，那么left指针向右移动，两个元素之和一定会大于最大值，此时我们就可以干掉右指针所指向的数；如果两个元素之和小于等于最大值，那么right指针向左移动，两个元素之和一定会小于等于最大值，此时我们就可以干掉左指针所指向的数。完成之后，我们就可以将固定值向左移动，在进行上述操作，直到固定数组的第三个元素。

完整代码实现：

java">class Solution {
    public int triangleNumber(int[] nums) {
        Arrays.sort(nums);//排序，优化
        int ret = 0,len = nums.length;
        for (int i = len-1; i >= 2; i--) {//先固定最大的数
            int left = 0,right = i-1;
            while(left < right){
                if(nums[left] + nums[right] > nums[i]){
                    ret += right - left;
                    right--;
                }else{
                    left++;
                }
            }
        }
        return ret;
    }
}