不重复打印排序数组中相加和为给定值的二元组和三元组

不重复打印排序数组中相加和为给定值的二元组和三元组

一、题目

给定排序数组 arr 和整数 K，不重复打印 arr 中所有相加和为 k 的不降序二元组

例如，arr = [-8, -4, -3, 0, 1, 2, 4, 5, 8, 9], k = 10 打印结果为
1 9
2 8

题目二：给定排序数组 arr 和整数 k，不重复打印 arr 中所有相加和为 k 的不降序三元组

二、思路

对于要打印二元组，比较简单。因为是排序数组，我们维护两个指针，一个指针 left 指向数组最左边，一个指针 right 指向数组最右边。循环条件是 left < right，在循环中，我们求得 arr[left] + arr[right] 为 sum，如果 sum 等于 k，则保存这个二元组。如果 sum 小于 k，因此我们需要一个更大一点的数，则将 left++。如果 sum 大于 k，我们需要一个小一点的数，则将 right--。还要注意题目要不不重复打印，因此我们判断的时候一定要注意当 sum 等于 k 时，判断 left 和 left-1 是否相等，相等就直接跳过。

对于要打印三元组，是一个 O(N2) 的时间复杂度。首先遍历数组，确定第一个元素 first。然后下一层循环从 first+1 开始，到数组结束，也就是如上的判断二元组的过程了。同样的，需要注意不重复。

三、代码

#include <vector>
#include <iostream>

class Solution {
public:
    // 不重复打印排序数组中相加和为给定值的所有二元组
    void print_unique_pair(const std::vector<int>& arr, int k) {
        if (arr.empty()) {
            return;
        }
        std::vector<std::pair<int, int>> res;
        int left = 0, right = arr.size()-1;
        for (; left < right;) {
            int val = arr[left] + arr[right];
            if (val > k) {
                right--;
            } else if (val < k) {
                left++;
            } else {
                if (left == 0 || arr[left] != arr[left-1]) {
                    res.emplace_back(arr[left], arr[right]);
                }
                left++, right--;
            }
        }
        for (const auto& x : res) {
            std::cout << x.first << " " << x.second << std::endl;
        }
    }

    // 不重复打印排序数组中相加和为给定值的所有三元组
    void print_unique_triple(const std::vector<int>& arr, int k) {
        if (arr.empty()) {
            return;
        }
        std::vector<std::vector<int>> res;
        for (int i = 0; i < arr.size(); ++i) {
            if (i != 0 && arr[i] == arr[i-1]) {
                continue;
            }
            int second = i+1, third = arr.size()-1;
            for (; second < third;) {
                int val = arr[i] + arr[second] + arr[third];
                if (val > k) {
                    third--;
                } else if (val < k) {
                    second++;
                } else {
                    if (arr[second] != arr[second-1]) {
                        res.push_back({arr[i], arr[second], arr[third]});
                    }
                    second++, third--;
                }
            }
        }
        for (const auto& x : res) {
            std::cout << x[0] << " " << x[1] << " " << x[2] << std::endl;
        }
    }
};

int main() {
    Solution s;
    std::vector<int> arr{-8, -4, -3, 0, 1, 1, 2, 4, 5, 8, 9};
    // s.print_unique_pair(arr, 10);
    s.print_unique_triple(arr, 10);
    return 0;
}