[code="java"]
boolean isMatch(double[]array,double target){
}
[/code]
match的规则是，先在array里面找，有没有一个元素array[i]==target,如果有则返回true，如果没有，继续找有没有任意两个元素相加==target,即array[i]+array[j]==target;如果还是没有继续找有没有任意三个元素相加==target,以此类推，只到array.length()个相加能不能==target为止，最终如果还是没找到，则返回false.
[code="java"]
/**
* match(深度匹配，参数：数组n[],查询值t,截止位置end,查询记录栈stack,深度deep)
* MyStack 以LinkedList为基础的stack简单的pop push操作，重写toString 使用list.toString()
/
public static void match(int[]n,int t,int end,MyStack stack,int deep){
for(int i=leftApproachT(n, t,end);i>=0;i--){
int temp=t-n[i];
int temp2 =deep;
stack.push(n[i]);
if(temp>0) {
match(n, temp,i,stack,temp2++);
}
else if(temp==0){
System.out.println(stack);
}
//将不需要的数据出栈
for(int j=deep;j>=0;j--)
stack.pop();
}
}
/*
* leftApproachT(从左开始查询最接近t的值所在数组n中对应的位置)
*/
public static int leftApproachT(int[]n,int t,int end){
for(int i=0;i if(n[i]>t) return i-1;
}
return end-1;
}
[/code]
判断出来没什么难度，把结果也都打出来
楼主换了个分多的号来了。。。
那个我觉得应该用深度搜索来解吧，你这个直接限定死了
如果只是返回boolean，有必要分那么多步判断么？而且你自己既然已经有思路，那么希望得到的是什么呢？
数组先排序~
例子：[1,2,5,6,7,10,12,15,20,23,24,26,29] 50
循环取1、2。。。、29
开始从深度挖掘取1 ，剩余49 寻找最接近49的数 29剩余 20 ok找到20 然后后退看有没有能代理20的 找15 剩余5 找到5， 在用12 。。。
基本就是过程
1 29 20
1 29 15 5
1 29 12 6 2
1 29 10 就不行了 然后 pop 29
1 26 23
。。。。
思路有点乱，利用堆栈~
本质上就是整数分解的问题
用动态规划。越到后面效率约高
反过来想，不是拆整数，用拆数组的办法试试
提供思路如下：
假设数组为a0, a1, a2,..., an-1, an,要匹配的数为M
采用下法来判断：
if an == M, 这时候当然找到了，返回true
如果不匹配，那么再check a0, a1, a2, ..., an-1 这个子数组与 M 或者 M - an是否匹配，如果匹配，就返回true，否则返回false；当然我没考虑效率哈。
[code="java"]
boolean isMatch(double[]array,double target){
return isMatch(array, target, array==null?0:array.length());
}
boolean isMatch(double[]array,double target, int index){
if(array == null || array.length() < index + 1 || index < 0){
return false;
}
if(array[index] == target){
return true;
}
return isMatch(array, target, index - 1) ||
return isMatch(array, target - array[index], index - 1);
}
[/code]
上面的只是一种思路，不保证代码可运行，以及效率
[code="java"]public static void match(int[]n,int t){
for(int i=leftApproachT(n, t);i>=0;i--){
int temp=t-n[i];
if(temp>0) {
match(n, temp);
}
else if(temp==0){System.out.println("find");}
}
}
public static int leftApproachT(int[]n,int t){
for(int i=0;i if(n[i]>t) return i-1;
}
return n.length-1;
}
[/code]
[code="java"]public class Test {
private static int count = 0;
/**
* @param args
*/
public static void main(String[] args) {
int[] a = { 1, 2, 5, 6, 7, 10, 12, 15, 20, 23, 24, 26, 29 };
System.out.print(isMatch(a, 50));
}
public static boolean isMatch(int[] array, int target) {
Arrays.sort(array);
LinkedList<Integer> stack = new LinkedList<Integer>();
findMatch(array, 0, target, stack);
return count > 0;
}
public static void findMatch(int[] array, int start, int target,
LinkedList<Integer> stack) {
for (int i = start; i < array.length; i++) {
if (array[i] == target) {
stack.push(array[i]);
printStack(stack);
count++;
stack.pop();
} else if (array[i] < target) {
stack.push(array[i]);
findMatch(array, i + 1, target - array[i], stack);
stack.pop();
} else {
return;
}
}
}
public static void printStack(List<Integer> stack) {
System.out.print("find a solution: ");
for (int i : stack) {
System.out.print(i + " ");
}
System.out.println();
}
}[/code]
find a solution: 29 7 6 5 2 1
find a solution: 26 10 6 5 2 1
find a solution: 24 12 6 5 2 1
find a solution: 23 12 7 5 2 1
find a solution: 20 15 7 5 2 1
find a solution: 20 12 10 5 2 1
find a solution: 24 10 7 6 2 1
find a solution: 29 12 6 2 1
find a solution: 26 15 6 2 1
find a solution: 20 15 12 2 1
find a solution: 24 23 2 1
find a solution: 26 12 6 5 1
find a solution: 23 15 6 5 1
find a solution: 15 12 10 7 5 1
find a solution: 29 15 5 1
find a solution: 24 20 5 1
find a solution: 26 10 7 6 1
find a solution: 24 12 7 6 1
find a solution: 23 20 6 1
find a solution: 20 12 10 7 1
find a solution: 24 15 10 1
find a solution: 29 20 1
find a solution: 26 23 1
find a solution: 20 10 7 6 5 2
find a solution: 15 12 10 6 5 2
find a solution: 26 10 7 5 2
find a solution: 24 12 7 5 2
find a solution: 23 20 5 2
find a solution: 23 12 7 6 2
find a solution: 20 15 7 6 2
find a solution: 20 12 10 6 2
find a solution: 29 12 7 2
find a solution: 26 15 7 2
find a solution: 26 12 10 2
find a solution: 23 15 10 2
find a solution: 20 12 7 6 5
find a solution: 29 10 6 5
find a solution: 24 15 6 5
find a solution: 26 12 7 5
find a solution: 23 15 7 5
find a solution: 23 12 10 5
find a solution: 20 15 10 5
find a solution: 15 12 10 7 6
find a solution: 29 15 6
find a solution: 24 20 6
find a solution: 23 20 7
find a solution: 23 15 12
find a solution: 26 24
true
我刚试过了，oom没有遇到，你看看把MyStack直接用linkedList，查询的结果集确实非常大
int[] n = { 1, 2, 5, 6, 7, 10, 12, 15, 20, 23, 24, 26, 29,30,31,33,40,55,59,66,88
,100,111,123,140,150,180,200,211,222,332,332,400,451,900,1223,2203,2234,5552};
int t=6000;
效率我觉得还是比较高的，一秒钟差不多10W条数据吧
这个结果集至少超过10G。。。
拿楼主给的例子，我用流将结果集写出，1个小时差不多写了10G
总的结果集大小我估计比50G大的多，这么大的结果集，想比较短的时间算出来基本不可能