注册 登录
编程论坛 JAVA论坛

假设有一个乱序的长度至少大于2的整数数组A,请你找出两数之和等于T的所有配对,并返回配对的数目。

JavaJack 发布于 2016-11-18 01:03, 1715 次点击
要求你认为算法复杂度最低的方法!!!

求大神指导!!!分享各自认为最好的方法
import java.util.*;
class Pairs
{
    int i=0,j=0;
    public int findPairs(int[] a,int sum,int T){
        Arrays.sort(a);                    //为数组排序
        while (i<a.length-1-j)
        {
            int x=a.length-1-j;                //数组自右逐一向前指定数组元素的标识
            int s=a[i]+a[x];            //排序后数组由前向指定数组元素与后向指定元素之和
            if (s>T)                    //若和大于指定元素,修改数组后向元素标识
            {
                j++;
            }else if(s<T){                //若和小于指定元素,修改数组前向元素标识
                i++;
            }else{                        //若s=T,则输出此数对,以及统计个数
                sum++;
                System.out.print("[" + a[i] + "," + a[x] + "]" + "   ");
                i++;
                j++;
            }
        }
        return sum;
    }
}
public class FindPairsDemo
{
    public static void main(String args[])
    {
        Pairs p=new Pairs();
        int arr[]={49,51,23,77,90,10,18,82};
        int num=0;
        int T=10;
        System.out.println("\n符合条件的数据有" + p.findPairs(arr,num,T) + "对!");
    }
}
2 回复
#2
learnJava2016-11-18 11:02
新手来学习一下。
楼主的方法很不错,很具有编程思想,先去排除掉不合格数据。学习了!在楼主的基础上我想到可以用折半的思想去考虑这个问题会不会让程序更快的结束掉?外加是不是可以先判断一下整个数组的数据都不合格的情况?
还有一种情况可能楼主没有考虑到,这也是我遇到觉得不好处理的地方
如果T=10  a=[5,5,5,5,5,5]
这样只会出现3对   不知道楼主的题意中所有的配对是不是本来就不包括这种情况?
本人新手,出来闹闹骚。
#3
JavaJack2016-11-18 17:34
回复 2楼 learnJava
非常感谢你的指教!
题目里的确说明了数组里没有重复的元素!在写程序的时候我也没有想过如果没有这个条件应该怎么做,完全没意识到这个问题,不得不说你想的很周到!
在此基础上折中的办法我也想过,只是最后程序没成功写出来,欢迎挑战一下
我也是个新手,大家互相学习,共同进步
1