首页 > 代码库 > 给定数组A，大小为n，现给定数X，判断A中是否存在两数之和等于X
给定数组A，大小为n，现给定数X，判断A中是否存在两数之和等于X
题目：给定数组A，大小为n，现给定数X，判断A中是否存在两数之和等于X
思路一：
1，先采用归并排序对这个数组排序，
2，然后寻找相邻<k,i>的两数之和sum，找到恰好sum>x的位置，如果sum=x则返回true，
3，找到位置后，保持i不变，从k处向前遍历，直到找到A[k]+A[i]等于x，并返回TRUE，如果找不到，则返回false。
论证步骤3：当前找到的位置恰好A[k]+A[i]>x，且前一位置的sum<x；
所以A[i]前面的数（不包括A[i]）无论取哪两个数都不可能使和等于x，只能小于x
对位置k向前寻找时，当寻找到A[k]+A[i]=sum，返回true；当寻找到sum<x时，令k=i，跳出对k的循环，继续寻找
当所有的路径寻找完之后，返回false，没找到
代码如下：
1 public boolean ExitSumX(int A[],int x) 2 { 3 //归并排序 4 MessSort(A); 5 6 int k=0; 7 for(int i=1;i<A.length;i++) 8 { 9 if(i!=k)10 {11 if(A[k]+A[i]==x)12 return true;13 else if(A[k]+A[i]<x)14 k=i;15 else16 {17 while(k>0)18 {19 k--;20 if(A[k]+A[i]==x)21 return true;22 else if(A[k]+A[i]<x)23 { k=i;break; };
24 }25 }26 }27 }28 return false; 29 }
算法分析：归并排序时间为：O(nlgn)，寻找算法时间复杂度为O(n2)，算法整体时间复杂度为：O(n2)，可见算法不算太好
思路二：
这种算法时间复杂度为O(nlgn)，思路来自 算法导论
给定数组A，大小为n，现给定数X，判断A中是否存在两数之和等于X
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。