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

题目描述

给定排序数组arr和整数k，不重复打印arr中所有相加和为k的不降序二元组
例如, arr = [-8, -4, -3, 0, 1, 2, 4, 5, 8, 9], k = 10，打印结果为：
1, 9
2, 8
[要求]
时间复杂度为O(n)O(n)，空间复杂度为O(1)O(1)

输入描述:

第一行有两个整数n, k
接下来一行有n个整数表示数组内的元素

输出描述:

输出若干行，每行两个整数表示答案
按二元组从小到大的顺序输出(二元组大小比较方式为每个依次比较二元组内每个数)

示例

输入
10 10
-8 -4 -3 0 1 2 4 5 8 9
输出
1 9
2 8

/*
解题思路：根据有序数组的特性，选用两个指针，一左一右往中间压缩数组，并根据判断条件去除重复的打印。
*/

import java.util.*;

public class Main{
    public static void main(String[] args){
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int k = scanner.nextInt();
        int[] arr = new int[n];
        for(int i=0;i<n;i++){
            arr[i] = scanner.nextInt();
        }
      
        int left = 0;
        int right = arr.length-1;
        while(left<right){
            if(arr[left]+arr[right]>k)
                right--;
            else if(arr[left]+arr[right]<k)
                left++;
            else{
		//去掉重复的打印
                if(left==0 || arr[left-1]!=arr[left])
                    System.out.println(arr[left]+" "+arr[right]);
                left++;
                right--;
            }
        }
    }
    
}

拓展

如果要打印三元组，又该怎样处理？

/*
三元组问题的处理类似于二元组的求解过程：
从前往后，依次选定一个值作为三元组的第一个值，再从后面的数组中找出与前面值相匹配的二元组。
*/
import java.util.*;

public class Main{
    public static void main(String[] args){
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int k = scanner.nextInt();
        int[] arr = new int[n];
        for(int i=0;i<n;i++){
            arr[i] = scanner.nextInt();
        }
        for(int i=0;i<n-1;i++){
	    //这里是第一个要注意的地方，保证第一个值不要重复
            if(i==0 || arr[i]!=arr[i-1])
                getTwoTuple(arr,k-arr[i],i);
        }
        
    }
    
    public static void getTwoTuple(int[] arr,int k,int i){
        int left = i+1;
        int right = arr.length-1;
        while(left<right){
            if(arr[left]+arr[right]<k)
                left++;
            else if(arr[left]+arr[right]>k)
                right--;
            else{
		//处理保证第二个值不要重复
                if(arr[left]!=arr[left-1] ){
                    System.out.println(arr[i]+" "+arr[left]+" "+arr[right]);
                }
		//左右同步压缩、保证第三个值不重复
                left++;
                right--;
            }
        }
    }
}