求更好的解法 - 黑马程序员技术交流社区

package org.mungo.algorithm;
import java.util.Arrays;
/**
* 将写有数字k1,k2...kn的n个纸片放入口袋中，可以从口袋中去4次纸片，每次几下纸片上数字后将纸片再放回口袋。
* 如果四个数字的和是m，就输出true，否则就输出false。检查是否有输出true的可能性。
* @author Lily
*
*/
public class Draw {
/**
* 1.穷举
* n[a] + n[b] + n[c] + n[d] == m
*
* @param n
* @param m
* @return
*/
private static boolean drawMethod(int[] n, int m) {
boolean result = false;
// 循环枚举所有可能
for (int a = 0; a < n.length; a++) {
for (int b = 0; b < n.length; b++) {
for (int c = 0; c < n.length; c++) {
for (int d = 0; d < n.length; d++) {
if (n[a] + n[b] + n[c] + n[d] == m) {
result = true;
}
}
}
}
}
return result;
}
/**
* 递归二分查找
*
* @param Array
* @param low
* @param high
* @param key
* @return
*/
private static boolean binarySearch(int Array[], int low, int high, int key) {
if (low <= high) {
int mid = (low + high) / 2;
if (key == Array[mid])
return true;
else if (key < Array[mid])
// 移动low和high
return binarySearch(Array, low, mid - 1, key);
else if (key > Array[mid])
return binarySearch(Array, mid + 1, high, key);
}
return false;
}
/**
* 2.n[d]=m - n[a] - n[b] - n[c]
*
* @param n
* @param m
* @return
*/
private static boolean drawMethod2(int[] n, int m) {
boolean result = false;
Arrays.sort(n); // 进行排序
for (int a = 0; a < n.length; a++) {
for (int b = 0; b < n.length; b++) {
for (int c = 0; c < n.length; c++) {
if (binarySearch(n, 0, n.length - 1, m - n[a] - n[b] - n[c])) {
result = true;
}
}
}
}
return result;
}
/**
* 3.n[c]+n[d]=m - n[a] - n[b]
*
* @param n
* @param m
* @return
*/
private static boolean drawMethod3(int[] n, int m) {
boolean result = false;
int nn[] = new int[n.length*n.length] ;
// 枚举n[c]+n[d]的和
for (int c = 0; c < n.length; c++) {
for (int d = 0; d < n.length; d++) {
nn[c * n.length + d] = n[c] + n[d];
}
}
Arrays.sort(nn);
for (int a = 0; a < n.length; a++) {
for (int b = 0; b < n.length; b++) {
if (binarySearch(nn, 0, nn.length - 1, m - n[a] - n[b])) {
result = true;
}
}
}
return result;
}
public static void main(String[] args) {
int[] numbers = { 1, 3, 5 };
System.out.println(drawMethod(numbers, 10));
System.out.println(drawMethod2(numbers, 10));
System.out.println(drawMethod3(numbers, 9));
}
}

复制代码