如何用双指针法在含重复元素数组中找和为q的有序对（O(N)时间O(1)空间）

需求与限制 #

• 核心需求：找出数组中所有满足公式A[i] + A[j] = q（i ≠ j）的有序对
• 示例：输入数组[1,3,3,3]，q=6，输出为[[3,3], [3,3], [3,3], [3,3], [3,3], [3,3]]
• 限制条件：不能使用额外数据结构，时间复杂度需为O(N)（不含排序时间），空间复杂度为O(1)（不计输出结果的存储空间）

现有无重复元素实现 #

已实现针对无重复元素数组的双指针算法，代码如下：

function findTuples(arr: number[], q: number): Array<[number, number]> {
    // 升序排序数组
    arr.sort((a, b) => a - b);

    let low = 0;
    let high = arr.length - 1;
    let result: Array<[number, number]> = [];

    // 双指针遍历，low小于high时循环
    while (low < high) {
        let sum = arr[low] + arr[high];

        if (sum === q) {
            result.push([arr[low], arr[high]]);
            result.push([arr[high], arr[low]]);

            low++;
            high--;
        } else if (sum < q) {
            // 和小于q，移动左指针
            low++;
        } else {
            // 和大于q，移动右指针
            high--;
        }
    }

    return result;
}

用户疑问 #

尝试用双指针法解决含重复元素的情况但未成功，询问该问题是否可行及对应的算法。

可行方案及算法实现 #

这个问题完全可以用双指针法解决，核心是统计重复元素的出现次数，一次性生成所有符合条件的有序对，而非像无重复元素场景那样仅添加两对。

算法思路 #

1. 先对数组排序（题目不计排序时间）
2. 使用双指针low和high分别从数组首尾开始遍历
3. 当arr[low] + arr[high] === q时：
   • 若arr[low] !== arr[high]：统计low侧元素的重复次数countLow、high侧元素的重复次数countHigh，有序对总数为countLow * countHigh * 2（(a,b)和(b,a)均为有效有序对），批量加入结果数组
   • 若arr[low] === arr[high]：元素相同时，有序对总数为count * (count - 1)（每个元素可与其余count-1个元素组成有序对，顺序不同算不同对），批量加入结果数组
4. 处理完当前重复元素后，直接将指针跳到下一个不同元素的位置，避免重复计算
5. 若两元素和小于q则移动low，大于q则移动high

实现代码 #

function findTuples(arr: number[], q: number): Array<[number, number]> {
    arr.sort((a, b) => a - b);
    let low = 0;
    let high = arr.length - 1;
    const result: Array<[number, number]> = [];

    while (low < high) {
        const sum = arr[low] + arr[high];
        if (sum === q) {
            const currentLowVal = arr[low];
            const currentHighVal = arr[high];
            
            // 统计左指针侧当前元素的重复次数
            let countLow = 0;
            while (low <= high && arr[low] === currentLowVal) {
                countLow++;
                low++;
            }
            // 统计右指针侧当前元素的重复次数
            let countHigh = 0;
            while (high >= low - 1 && arr[high] === currentHighVal) {
                countHigh++;
                high--;
            }

            if (currentLowVal !== currentHighVal) {
                // 不同元素：批量生成两种顺序的有序对
                for (let i = 0; i < countLow * countHigh; i++) {
                    result.push([currentLowVal, currentHighVal]);
                    result.push([currentHighVal, currentLowVal]);
                }
            } else {
                // 相同元素：批量生成所有i≠j的有序对
                for (let i = 0; i < countLow * (countLow - 1); i++) {
                    result.push([currentLowVal, currentHighVal]);
                }
            }
        } else if (sum < q) {
            low++;
        } else {
            high--;
        }
    }

    return result;
}

复杂度验证 #

• 时间复杂度：排序后双指针遍历数组，每个元素最多被访问一次，遍历过程为O(N)，符合要求
• 空间复杂度：除存储结果的数组外，仅使用常数个变量，空间复杂度为O(1)，符合要求

示例测试 #

输入array = [1,3,3,3]，q=6：

• 排序后数组为[1,3,3,3]
• 初始low=0，high=3，1+3=4<6，low移动到1
• 此时arr[1]+arr[3]=6=q，统计得3的出现次数为3，有序对数量为3*(3-1)=6，结果数组添加6个[3,3]，与示例输出一致

内容的提问来源于stack exchange，提问作者Afshin Jalili