博客

【题目】

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

例如：

arr=[-8,-4,-3,0,1,2,3,4,5,8,9]，k=10

打印结果为：

1，9

2，8

【补充题目】


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

例如：

arr=[-8,-4,-3,0,1,2,4,5,8,9]，k=10

打印结果为：

-4，5，9

-3，4，9

-3，5，8

0，1，9

0，2，8

1，4，5

【代码】

    public static void main(String[] args) {
        int[] arr=new int[]{-8,-4,-3,0,1,2,4,5,8,9};
        printUniquePair(arr,10);//1,9;2,8
        printUniqueTriad(arr,10);
    } 

    //不重复打印排序数组中相加和为给定值的所有二元组
    public static void printUniquePair(int[] arr,int k){
        if(arr==null||arr.length<2){
            return;
        }
        int left=0;
        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(left==0||arr[left-1]!=arr[left]){
                    //保证不重复打印：检查arr[left]是否和arr[left-1]相等
                    System.out.println(arr[left]+","+arr[right]);
                }
                left++;
                right--;
            }
        }
    }

    //不重复打印排序数组中相加和为给定值的所有三元组
    public static void printUniqueTriad(int[] arr,int k){
        if(arr==null||arr.length<3){
            return;
        }
        //先定三元组的第1个元素，接下来找和为k-arr[i]的二元组
        for(int i=0;i<arr.length-2;i++){
            if(i==0||arr[i]!=arr[i-1]){
                //保证不重复
                printRest(arr,i,i+1,arr.length-1,k-arr[i]);
            }
        }       
    }

    private static void printRest(int[] arr, int first, int left, int right, int k) {
        while(left<right){
            if(arr[left]+arr[right]<k){
                left++;
            }else if(arr[left]+arr[right]>k){
                right--;
            }else{
                if(left==first+1 || arr[left-1]!=arr[left]){
                    //保证二元组不重复
                    System.out.println(arr[first]+","+arr[left]+","+arr[right]);
                }
                left++;
                right--;
            }
        }
    }