我的算法笔记

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

2018-05-09  本文已影响10人  Airycode

【题目】
给定排序数组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=arr.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,否则过程结束。
【代码实现】

package 数组和矩阵;

public class Main7 {

    public static void main(String[] args) {
        int[]arr={1,1,1,9,9,9};
        int k=10;
        print2Number(arr,k);
    }

    /**不重复打印二元组*/
    private static void print2Number(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--;
            }
            
        }
        
    }
    
}


上一篇下一篇

猜你喜欢

热点阅读