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

个人主页：手握风云

专栏：算法

目录

一、双指针算法思想

二、算法题精讲

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

2.2. 盛最多水的容器

​编辑

2.3. 移动零

2.4. 有效的三角形个数

---

一、双指针算法思想

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

二、算法题精讲

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

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

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

2.3. 移动零

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

  

完整代码实现：

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循环来查找，此时的时间复杂度为。

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

完整代码实现：

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