给定一个整数型的数组，和一个特定的整数值。编程求出数组中任两个元素的差等于给定整数值的值对？
如题，自己初步想了下，貌似是一道关于排列组合的问题，不知道有没有更完美的解决方法？
请赐教
改进的算法，免去了很多不必要的比较。提高算法的效率，保证了结果的正确性。
[code="java"]
import java.util.Arrays;
public class TestClass{
public static void printPairs(int number, int[] list) {
if (list.length < 2)
return;
boolean b = false;
Arrays.sort(list);
//首先取最大值，看是否存在这样的值对
if(number>(list[list.length-1]-list[0])){
System.out.println("不存在这样的值对");
return;
}
//下面从第一个元素开始判断，和后面的值做差。如果差值超过number，停止与后面更大的数值比较
for(int i = 0;i<list.length-2;i++)//最后一个元素不用取。
{
int j=i;
while(number>=(list[j]-list[i])){
if(number==(list[j]-list[i])){
b = true;
System.out.println(list[j]+" "+list[i]);}
if(++j>list.length-1)break;//和最后一个数组做差，退出。
}
}
if(!b){System.out.println("不存在这样的值对");}
}
public static void main(String[] args) {
int number = 51;
int[] list = { 45, 60, 42, 83, 36, 10, 16, 21, 15 };
printPairs(number, list);
}
}
[/code]
先排序，再从高到低做减法。
数据小的话用这个。
int i = 0
foreach(int a :arr){
foreach(int b :arr){
if((a-b)== c/*给定的值*/){
i++;
System.out.println(a+" "+b);
}
}
}
程序如下,排序的时间复杂度O(nlgn)，后面进行减法需要一次遍历，时间复杂度O(n)，总的时机复杂度O(nlgn)
[code="java"]public class TestClass{
public static void printPairs(int number, int[] list) {
if (list.length < 2)
return;
// 使用java工具类排序，也可以自己排序
Arrays.sort(list);
for (int i = list.length; i > 1; i--) {
if (list[i - 1] - list[i - 2] == number) {
System.out.println("pair: " + list[i - 1] + ", " + list[i - 2]);
}
}
}
public static void main(String[] args) {
int number = 5;
int[] list = { 45, 60, 42, 83, 36, 10, 16, 21, 15 };
printPairs(number, list);
}
}[/code]
运行结果：
pair: 21, 16
pair: 15, 10
[quote]能解释一下为什么从高到底依次做差就一定能保证成对的元素呢？会不会有漏掉的呢？[/quote]
恩，你说的对，考虑这个问题时忽略了两个数可能间隔如果各个数的情况，重新改写如下。
[code="java"]public class TestClass{
public static void printPairs(int number, int[] list) {
if (list.length < 2)
return;
// 使用java工具类排序，也可以自己排序
Arrays.sort(list);
for (int i = list.length - 1; i > 0; i--) {
for (int j = i - 1; j >= 0; j--) {
if (list[i] - list[j] == number) {
System.out.println("pair: " + list[i] + ", " + list[j]);
} else if (list[i] - list[j] > number) {
continue;
}
}
}
}
public static void main(String[] args) {
int number = 5;
int[] list = { 45, 41, 60, 42, 40, 83, 36, 10, 16, 21, 15 };
printPairs(number, list);
}
}[/code]
运行结果：
pair: 45, 40
pair: 41, 36
pair: 21, 16
pair: 15, 10
另外，上面的程序还可以优化，当i固定的时候，可以不从i下一个开始减，因为这样减总的时机复杂度就成了O(n*n)， 减的时候开始使用二分法，也就是说，当i固定时，从后面的元素中间元素开始减，依次类推。
使用二分法减总的时机复杂度还是O(nlgn)。