数组双指针算法的研究

双指针算法在数组/链表操作中应用广泛，很多时候，为了完成某个目的，常常需要不断的循环检查数组或是链表，又或者需要拷贝出额外的存贮空间来保存中间结果。在其中的一些情况下，如果能够合理的应用数组双指针，则可以极大的减少算法的时间复杂度和空间复杂度。

 

根据初始双指针的位置，可以将之分为双头部指针，双尾部指针以及头尾指针.

 

今天我们就来看几个利用数组双指针算法的例子。

 

案例1： 给定一个数组，求出索引i和j，使得i和j之间的子串为符合某个特定条件的子串。

 

这种类型有很多，主要是为了找出符合特定条件的子串，下面是几个特定条件的例子：

1. Sum（i -> j） > k 的最短子数组， k为某常量

2. Sum（i -> j） < k 的最长子数组， k为某常量

3. Sum（i -> j） = k 且 j - i = ，m 的最子数组， k为某常量

4.（j - i）* min(array[i], array[j]) 最大的子数组

 

以第一道题为例，就是为了找出和大于某个特定常量的最短子数组。

 

常见的解决方案可以通过找出所有符合条件的子数组，然后根据这些子数组的长度，选出最短的那个。算法的时间复杂度为O(nlogn),空间复杂度为O(n^2)

 

当然我们也可以利用双头部指针算法，

 

     - 初始索引i和j指向数组头部，计数器maxLength为0.

     - 迭代： 

          - 如果i与j之间的子数组的和大于k，则判断j -i + 1是否小于maxLength，若是，则将maxLength更新为j -i + 1，i++并移向下一组candidate。

          - 如果i与j之间的子数组的和小于等于k，则j++。

          - 当j到达数组尾部时，结束迭代。

     - 在迭代过程中，计算i与j之间子数组的和并不需要每次都重新计算，而是只要相应增量的加上j位置的值或是减去i位置的值即可。

 

我们将时间复杂度降低到O(n),空间复杂度为O(1)。 看一下代码：

 

public class MinSubArrayLen {
    public static void main(String[] args) {
        MinSubArrayLen ms = new MinSubArrayLen();
        System.out.println(ms.minSubArrayLen(7, new int[]{2, 3, 1, 2, 4, 3}));
    }

    /**
     * 双指针-双头部算法
     *
     * @param s
     * @param nums
     * @return
     */
    public int minSubArrayLen(int s, int[] nums) {
        if (nums.length == 0) return 0;

        int i = 0;
        int j = 0;
        int min = Integer.MAX_VALUE;

        int sum = nums[0];
        while(true) {
            if (sum < s) {
                j++;
                if (j == nums.length) break;

                sum += nums[j];
            } else {
                min = Math.min(min, j - i + 1);
                sum -= nums[i];
                i++;
            }
        }

        return min == Integer.MAX_VALUE ? 0 : min;
    }

 

 

许多类似的题目（找出符合特定条件的子串）都可以利用这样的算法来解决，区别仅仅是在于初始状态指针的位置。

 

第四道题目的原题是这样的： 

     给定 n个非负整数a1，a2，... an， 每个ai代表位置为i，高度为ai的柱子，那么求i和j使得ai到aj所能形成的正方形最大（即（j - i）* min(ai，aj)）

 

这个问题也还是可以通过双指针算法来解决，区别在于指针的初始状态为一头一尾

     - 初始索引i和指向数组头部，j指向数组尾部，计数器maxArea为0.

     - 迭代： 

          - 计算当前Area，若大于maxArea则替换。

          - 若a[i] < a[j], 则i++， 否则j--。

          - 当i与j相遇时，迭代结束。

 

时间复杂度降低到O(n),空间复杂度为O(1)。 看一下代码：

 

public class Solution {
    public int maxArea(int[] height) {
        int len = height.length, low = 0, high = len -1 ;
        int maxArea = 0;
        while (low < high) {
            maxArea = Math.max(maxArea, (high - low) * Math.min(height[low], height[high]));

            if (height[low] < height[high]) {
                int lowbaseline = height[low];
                while(true) {
                    if (low >= high || height[low] > lowbaseline) break;
                    low++;
                }
            } else {
                int highbaseline = height[high];
                while(true) {
                    if (high <= low || height[high] > highbaseline) break;
                    high--;
                }

            }
        }

        return maxArea;
    }
}

 

 

 

还有一类问题，它们并没有找出某个特定子串的要求，但是为了达到常量级的空间复杂度，通常也可以使用双指针算法：

5. 将数组拆分为左奇右偶

6. 检查链表是否有环

7. 快速排序

 

 

第五个例子要求找出数组中所有的奇数和偶数，并将奇数放在数组的前端，偶数放在数组的后端。

 

这个题目其实很简单，但是要想达到常量级的空间复杂度，则要求必须是一个on place的算法，我们也可以利用双指针来做到这一点。

 

基本的思路其实是和快速排序的partition一致，关于快排的讨论已经很多了，这里不再赘述。 我们看一下快排的partition代码。为了解释算法本身，并没有做任何优化：

 

public class QuickSort {

    /**
     * 取数组的最后一位做为中位数。
     * 从开始进行遍历，如果某值小于该中位数，i向前一步走，i与j的数值互换。
     * 如果某值大于该中位数，则j++。
     * 算法很精巧，始终维持i与j之间正好是所有大于中位数的值。
     *
     * @param array
     * @param start
     * @param end
     * @return
     */
    private int partition(int[] array, int start, int end) {
        int mediumVal = array[end];
        int i = start - 1;

        for (int j = start; j < end; j++) {
            if (array[j] <= mediumVal) {
                i++;
                exchange(array, i, j);
            }
        }

        exchange(array, i + 1, end);

        return i + 1;
    }
}

 

 

第六个例子实在是经典算法考题，判断一个链表中是否有环，只要用两个指针，一个每次走一步，另一个每次走两步，看足够多的步之后，两个指针是否会相遇即可。同样也不需要额外的存储空间。

 

这里就总结了关于双指针算法的7种常见使用场景，欢迎大家提供更多的好例子。