03 双指针

方向相反的双指针经常用来求排序数组中的两个数字之和。一个指针P1指向数组的第1个数字，另一个指针P2指向数组的最后一个数字，然后比较两个指针指向的数字之和及一个目标值。如果两个指针指向的数字之和大于目标值，则向左移动指针P2；如果两个指针指向的数字之和小于目标值，则向右移动指针P1。此时两个指针的移动方向是相反的。

方向相同的双指针通常用来求正数数组中子数组的和或乘积。初始化的时候两个指针P1和P2都指向数组的第1个数字。如果两个指针之间的子数组的和或乘积大于目标值，则向右移动指针P1删除子数组最左边的数字；如果两个指针之间的子数组的和或乘积小于目标值，则向右移动指针P2在子数组的右边增加新的数字。此时两个指针的移动方向是相同的。下面用双指针来解决几道典型的数组面试题。

面试题 6 排序数组中的两个数字之和

题目： 输入一个递增排序的数组和一个值k，请问如何在数组中找出两个和为k的数字并返回它们的下标？假设数组中存在且只存在一对符合条件的数字，同时一个数字不能使用两次。例如，输入数组[1，2，4，6，10]，k的值为8，数组中的数字2与6的和为8，它们的下标分别为1与3。

分析

方法一

两层循环，依次求出对应的下标，时间复杂度 $O(n^2)$

方法二

使用两个指针: 我们用两个指针P1和P2分别指向数组中的两个数字。指针P1初始化指向数组的第1个（下标为0）数字，指针P2初始化指向数组的最后一个数字。如果指针P1和P2指向的两个数字之和等于输入的k，那么就找到了符合条件的两个数字。如果指针P1和P2指向的两个数字之和小于k，那么我们希望两个数字的和再大一点。由于数组已经排好序，因此可以考虑把指针P1向右移动。因为在排序数组中右边的数字要大一些，所以两个数字的和也要大一些，这样就有可能等于输入的数字k。同样，当两个数字的和大于输入的数字k时，可以把指针P2向左移动，因为在排序数组中左边的数字要小一些。

时间复杂度 $O(n)$, 空间复杂度 $O(1)$。

代码

package com.zj.offer.code;

/**
 * 作者: zhoujun134
 * 时间: 2023/12/5 23:38
 */
public class Test6 {
    public static void main(String[] args) {
        int[] nums = {1, 2, 5, 6, 10};
        int[] result = getSumMethod2(nums, 8);
        System.out.println(result[0]);
        System.out.println(result[1]);

    }

    public static int[] getSumMethod1(int[] nums, int k) {
        int[] result = new int[2];
        for (int i = 0; i < nums.length; i++) {
            boolean flag = false;
            for (int j = i + 1; j < nums.length; j++) {
                int a = nums[i];
                int b = nums[j];
                if (a + b == k) {
                    result[0] = i;
                    result[1] = j;
                    flag = true;
                    break;
                }
            }
            if (flag) {
                break;
            }
        }
        return result;
    }

    /**
     * 二分查找法
     */
    public static int[] getSumMethod2(int[] nums, int k) {
        int i = 0, j = nums.length - 1;
        while (i < j && nums[i] + nums[j] != k) {
            if (nums[i] + nums[j] < k) {
                i++;
            } else {
                j--;
            }
        }
        return new int[] {i, j};
    }
}

面试题 7: 数组中和为 0 的 3 个数字

题目： 输入一个数组，如何找出数组中所有和为 0 的 3 个数字的三元组？需要注意的是，返回值中不得包含重复的三元组。例如，在数组[-1，0，1，2，-1，-4]中有两个三元组的和为0，它们分别是[-1，0，1]和[-1，-1，2]。

分析

这个题目是面试题 6 的加强版。如果输入的数组是排序的，就可以先固定一个数字i，然后在排序数组中查找和为 -i 的两个数字。我们已经有了用 $O(n)$ 时间在排序数组中找出和为给定值的两个数字的方法，由于需要固定数组中的每个数字，因此查找三元组的时间复杂度是 $O(n^2)$。

前面只需要 $O(n)$ 时间在数组中找出和为给定值的两个数字的方法只适用于排序数组。可是这个题目并没有说给出的数组是排序的，因此需要先对数组排序。排序算法的时间复杂度通常是$O(nlogn)$，因此这种解法的总的时间复杂度是$O(nlogn+ n^2)$，仍然是 $O(n^2)$。

还剩下一个问题是如何去除重复的三元组。前面提到需要使用两个指针来找出和为给定值的两个数字。在找到一个和为 0 的三元组之后，就需要移动这两个指针，以便找出其他符合条件的三元组。在移动指针的时候需要跳过所有相同的值，以便过滤掉重复的三元组。

代码

package com.zj.offer.code;

import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;

/**
 * 作者: zhoujun134
 * 时间: 2023/12/6 23:55
 */
public class Test7 {
    public static void main(String[] args) {
        int[] nums = {-1, 0, 1, 2, -1, -4};
        List<List<Integer>> lists = threeSum(nums);
        System.out.println(lists);

    }

    public static List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> result = new LinkedList<>();
        if (nums.length >= 3) {
            Arrays.sort(nums);
            int i = 0;
            while (i < nums.length - 2) {
                twoSum(nums, i, result);
                int temp = nums[i];
                while (i < nums.length && nums[i] == temp) {
                    ++i;
                }
            }
        }
        return result;
    }

    private static void twoSum(int[] nums, int i, List<List<Integer>> result) {
        int j = i + 1;
        int k = nums.length - 1;
        while (j < k) {
            if (nums[i] + nums[j] + nums[k] == 0) {
                result.add(Arrays.asList(nums[i], nums[j], nums[k]));
                int temp = nums[j];
                while (nums[j] == temp && j < k) {
                    ++j;
                }
            } else if (nums[i] + nums[j] + nums[k] < 0) {
                ++j;
            } else {
                --k;
            }
        }
    }
}

上述代码先对数组进行排序。在固定用变量i指向的数字之后，函数twoSum在排序后的数组中找出所有下标大于i并且和为-nums[i]的两个数字（下标分别为j和k）。如果nums[i]、nums[j]、nums[k]的和大于0，那么下标k向左移动；如果nums[i]、nums[j]、nums[k]的和小于0，那么下标j向右移动。如果3个数字之和正好等于0，那么向右移动下标j，以便找到其他和为-nums[i]的两个数字。

由于要避免重复的三元组，因此函数twoSum使用一个while循环让下标j跳过重复的数字。基于同样的原因，函数threeSum中也有一个while循环让下标i跳过重复的数字。

面试题 8：和大于或等于k的最短子数组

题目： 输入一个正整数组成的数组和一个正整数 k，请问数组中和大于或等于 k 的连续子数组的最短长度是多少？如果不存在所有数字之和大于或等于 k 的子数组，则返回 0。例如，输入数组 [5，1，4，3]，k 的值为 7，和大于或等于 7 的最短连续子数组是 [4，3]，因此输出它的长度 2。

分析

子数组由数组中一个或连续的多个数字组成。一个子数组可以用两个指针表示。如果第1个指针 P1 指向子数组的第1个数字，第2个指针 P2 指向子数组的最后一个数字，那么子数组就是由这两个指针之间的所有数字组成的。指针 P1 和 P2 初始化的时候都指向数组的第1个元素。如果两个指针之间的子数组中所有数字之和大于或等于k，

那么把指针 P1 向右移动。每向右移动指针 P1 一步，相当于从子数组的最左边删除一个数字，子数组的长度也减1。由于数组中的数字都是正整数，从子数组中删除一些数字就能减小子数组之和。由于目标是找出和大于或等于k的最短子数组，因此一直向右移动指针P1，直到子数组的和小于k为止。

如果两个指针之间的子数组中所有数字之和小于k，那么把指针P2向右移动。指针P2每向右移动一步就相当于在子数组的最右边添加一个新的数字，子数组的长度加1。由于数组中的所有数字都是正整数，因此在子数组中添加新的数字能得到更大的子数组之和。

代码

package com.zj.offer.code;

/**
 * 作者: zhoujun134
 * 时间: 2023/12/7 00:13
 */
public class Test8 {
    public static void main(String[] args) {
        int k = 7;
        int[] nums = {5, 1, 4, 3};
        int minSubArrayLen = minSubArrayLen(k, nums);
        System.out.println(minSubArrayLen);
    }

    public static int minSubArrayLen(int k, int[] nums) {
        int left = 0;
        int sum = 0;
        int minLength = Integer.MAX_VALUE;
        for (int right = 0; right < nums.length; right++) {
            sum += nums[right];
            while (left <= right && sum >= k) {
                minLength = Math.min(minLength, right - left + 1);
                sum -= nums[left++];
            }
        }
        return minLength == Integer.MAX_VALUE ? 0 : minLength;
    }
}

在上述代码中，变量left是子数组中第1个数字的下标，相当于指针P1，而变量right是子数组中最后一个数字的下标，相当于指针P2。变量sum是位于两个指针之间的子数组中的所有数字之和。

最后分析这种解法的时间复杂度。假设数组的长度为n，尽管上述代码中有两个嵌套的循环，该解法的时间复杂度仍然是 $O(n)$。这是因为在这两个循环中，变量left和right都是只增加不减少，变量 right 从 0 增加到 n-1，变量 left 从 0 最多增加到 n-1，因此总的执行次数是 $O(n)$。

面试题 9：乘积小于 k 的子数组

题目： 输入一个由正整数组成的数组和一个正整数 k，请问数组中有多少个数字乘积小于 k 的连续子数组？例如，输入数组 [10，5，2，6]，k 的值为 100，有 8 个子数组的所有数字的乘积小于 100，它们分别是[10]、[5]、[2]、[6]、[10，5]、[5，2]、[2，6]和[5，2，6]。

分析

虽然这个题目是关于子数组数字的乘积的，和面试题8（关于子数组数字之和）看起来不太一样，但求解的思路大同小异，仍然可以利用两个指针求解。

和面试题 8 一样，用指针 P1 和 P2 指向数组中的两个数字，两个指针之间的数字组成一个子数组。指针P1永远不会走到指针 P2 的右边。两个指针初始化都指向数组的第1个数字（下标为0的数字）。

如果两个指针之间的子数组中数字的乘积小于k，则向右移动指针P2。向右移动指针P2相当于在子数组中添加一个新的数字，由于数组中的数字都是正整数，因此子数组中数字的乘积就会变大。

如果两个指针之间的子数组中数字的乘积大于或等于k，则向右移动指针P1。向右移动指针P1相当于从子数组中删除最左边的数字，由于数组中的数字都是正整数，因此子数组中数字的乘积就会变小。

由于我们的目标是求出所有数字乘积小于 k 的子数组的个数，一旦向右移动指针P1到某个位置时子数组的乘积小于k，就不需要再向右移动指针P1。这是因为只要保持指针P2不动，向右移动指针P1形成的所有子数组的数字乘积就一定小于k。此时两个指针之间有多少个数字，就找到了多少个数字乘积小于k的子数组。

代码

package com.zj.offer.code;

/**
 * 作者: zhoujun134
 * 时间: 2023/12/7 00:26
 */
public class Test10 {
    public static void main(String[] args) {
        int k = 100;
        int[] nums = {10, 5, 2, 6};
        int result = numSubArrayProductLessThanK(k, nums);
        System.out.println(result);
    }

    public static int numSubArrayProductLessThanK(int k, int[] nums) {
        long product = 1;
        int left = 0;
        int count = 0;
        for (int right = 0; right < nums.length; right++) {
            product *= nums[right];
            while (left <= right && product >= k) {
                product /= nums[left++];
            }
            count += right >= left ? right - left + 1 : 0;
        }
        return count;
    }
}

和面试题 8 的代码类似，在上述代码中，变量 left 是子数组中第1个数字的下标，相当于指针 P1，而变量 right 是子数组中最后一个数字的下标，相当于指针P2。

变量 product 是位于两个指针之间的子数组中的所有数字的乘积。

和面试题 8 一样，这种解法的时间复杂度也是 $O(n)$。请读者自行分析，这里不再重复介绍。