CloudLander's Blog
0%

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

发表于 分类于

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

给定排序数组arr和整数k，不重复打印arr中所有相加和为k的不降序二元组。
例如，arr=[-8,-4,-3,0,1,2,4,5,8,9],k=10,打印结果为：
1,9
2,8

1.利用双指针法，设置遍历left=0和right=length-1
2.比较arr[left]+arr[right]的值(sum)与k的大小
如果sum等于k，打印arr[left],arr[right], left++,right–.
如果sum大于k，right–
如果sum小于k，left++
3.如果left< right,则一直重复步骤2，否则过程结束
为了保证不重复打印，只需在打印前增加一个检查：arr[left]是否与它前一个值相等，如果相等就不打印
解释：因为整体过程是两头向中间压缩的过程，如果arr[left]+arr[right]=k,又有arr[left]==arr[left-1],那么之前一定打印过这个二元组，则不用再重复打印
时间复杂度O(N)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public 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]){
                System.out.println(arr[left]+","+arr[right]);
            }
            left++;
            right--;
        }
    }
}

三元组的问题类似于二元组的求解过程

例如 arr=[-8,-4,-3,0,1,2,4,5,8,9] k=10
当三元组的第一个值为-8时，寻找-8后面的子数组中所有相加为18的不重复二元组
当三元组的第一个值为-4时，寻找-4后面的子数组中所有相加为14的不重复二元组
当三元组的第一个值为-3时，寻找-3后面的子数组中所有相加为13的不重复二元组
依次类推：
如果不重复打印？首先保证每次寻找过程开始前，选定的三元组中第一个值不重复，其次就是原问题的打印检查一样，保证不重复打印二元组
时间复杂度为O(n^2)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
public void printUniqueTriad(int[] arr, int k){
    if(arr==null || arr.length<2){
        return;
    }
    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]);
        }
    }
}

public void printRest(int[] arr, int f, int l, int r, int k){
    while(l<r){
        if(arr[l]+arr[r]<k){
            l++;
        }else if(arr[l]+arr[r]>k){
            r--;
        }else{
            if(l==f+1 || arr[l-1]!=arr[l]){
                System.out.println(arr[f]+","+arr[l]+","+arr[r]);
            }
            l++;
            r--;
        }
    }
}