程序员代码面试指南 003-004

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

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

题目关于重复元素该如何处理都没说清楚，只能通过提交来试标准答案。

这两道题很像。找二元组要求O(n)的时间和O(1)的空间，所以只能遍历一次，并且不能记录查找结果，所以必须要利用排序的性质——使用头尾指针向中间压缩即可。每个元素只能用1次，二元组之间不重复，二元组内两个元素或许可以重复。

#include <iostream>
#include <vector>

using namespace std;

int main()
{
    int n, k;
    cin >> n >> k;
    vector<int> vec(n);
    for(int i = 0; i < n; i++)
    {
        cin >> vec[i];
    }
    int begin = 0, end = n;
    while(begin < end - 1){
        if(vec[begin] + vec[end - 1] > k){
            end--;
        }
        else if(vec[begin] + vec[end - 1] < k){
            begin++;
        }
        else{
            cout << vec[begin] << ' ' << vec[end - 1] << endl;
            int tmp = vec[begin];
            while(begin < end - 1 && vec[begin] == tmp) begin++;
        }
    }
    return 0;
}

找三元组也要求O(n ^ 2)的时间和O(1)的空间，可以借助二元组的解法，从左开始，依次选择三元组中第1个的元素，然后对后面的数组应用二元组的解法。每个元素只能用1次，三元组之间互不相同，三元组的第1个元素不能和第2个元素相同，但是第2个和第3个或许可以相同。

#include <iostream>
#include <vector>

using namespace std;

int main()
{
    int n, k;
    cin >> n >> k;
    vector<int> vec(n);
    for(int i = 0; i < n; i++)
    {
        cin >> vec[i];
    }
    int begin = 0, mid, end, part, tmp;
    while(begin < n - 2){
        mid = begin + 1;
        while(mid < n - 1 && vec[mid] == vec[begin]) mid++;
        end = n;
        part = k - vec[begin];
        while(mid < end - 1){
            if(vec[mid] + vec[end - 1] > part){
                end--;
            }
            else if(vec[mid] + vec[end - 1] < part){
                mid++;
            }
            else{
                cout << vec[begin] << ' ' << vec[mid] << ' ' << vec[end - 1] << endl;
                tmp = vec[mid];
                while(mid < end - 1 && vec[mid] == tmp) mid++;
            }
        }
        tmp = vec[begin];
        while(begin < n - 2 && vec[begin] == tmp) begin++;
    }
}