2

我编写了下面的代码来查看一个数组是否有 2 个数字相加。我不知道如何捕捉促成该总和的元素。有什么想法吗

示例 = {1,11,4,7,8,10} Sum = 21 Count=2

此代码返回 true 或 false，但不捕获对总和有贡献的数字。我怎样才能做到这一点？

public static boolean isSum(int[] a,int val,int count,int index){
    if(count == 0 && val ==0){
        return true;
    }
    if(index>=a.length)
        return false;
    else{
        return isSum(a,val-a[index],count-1,index+1)||isSum(a,val,count,index+1);
    }
}

我很欣赏下面列出的所有漂亮的解决方案。早上四处闲逛，找到了一种优雅的方法来解决这个问题，因为它可以解决任何数量的元素。只是想在这里分享解决方案以供您发表评论

public class IsSum {

static ArrayList<Integer> intArray;

public static void main(String[] args) {
    // TODO code application logic here
    int[] a = {1,44, 4, 7, 8, 10};
    intArray = new ArrayList<Integer>();
    if (isSum(a,54,2, 0)) {
        System.out.println("Is Present");
    }
    Iterator<Integer> arrayIter = intArray.iterator();
    while (arrayIter.hasNext()) {
        System.out.println(arrayIter.next());
    }
}

public static boolean isSum(int[] a, int val, int count, int index) {
    if (count == 0 && val == 0) {
        return true;
    }

    if (index >= a.length) {
        return false;
    } else {
        if (isSum(a, val - a[index], count - 1, index + 1)) {
            intArray.add(a[index]);
            return true;
        } else {
            return isSum(a, val, count, index + 1);
        }
    }
}

}

4

4 回答 4

1 
/**
 * Class used to hold the result details.
 */
private static class Result {
    boolean isSum;

    int[][] pairs;

    int noOfPairs;

    Result(int value) {
        pairs = new int[value][2];
    }
}

public static Result isSum(int[] array, int val, int count) {
    Result result = new Result(count);
    int index = 0;
    for (int i = 0; i < array.length; i++) {
        for (int j = i + 1; j < array.length; j++) {
            //check if pair values add to given sum
            if (array[i] + array[j] == val) {
                int[] temp = new int[2];
                temp[0] = array[i];
                temp[1] = array[j];
                result.pairs[index++] = temp;
                result.noOfPairs++;
                count--;
                if (count == 0) {
                    //we got required no of pairs..now exit
                    result.isSum = true;
                    return result;
                }
            }
        }
    }
    return result;
}
于 2013-08-21T05:21:25.587 回答
1

补丁有点难看 - 但它可以工作，如果有这样两个元素 - 结果将返回数组中这些元素的索引：

public static int[] isSum(int[] a,int val,int count,int index, int[] arr){
    int[] res = new int[2];
    if(count == 0 && val ==0){
        return arr;
    }
    else if(index >=a.length || count == 0) {
        return res;
    }
    else{
        res[0] = arr[0];
        res[1] = arr[1];
        if(count==1){
            arr[1] = index;
        }
        else{
            arr[0] = index;
        }
        int[] s1 = isSum(a,val-a[index],count-1,index+1, arr);
        int[] s2 = isSum(a,val,count,index+1, res);
        res = (s1[1] != 0 ? s1 : s2);
    }
    return res;
}

public static void main(String...args){
    int[] a = {1,11,4,7,8,10};
    int[] s = new int[2];
    int [] res = isSum(a, 21, 2, 0, s);
    System.out.println("result: "+(res[1] != 0));
    if((res[1] > 0)){
        System.out.print(res[0]+" "+res[1]);
    }
}

输出

result: true
1 5

另一种（更优雅）的方式：

public static int[] isSum(int[] a,int val){
    int[] res = new int[2];
    for(int i=0; i<a.length; i++){
        int tmp = a[i];
        int index = search(a, val-tmp);
        if(index != -1){
            return new int[] {i, index};//success
        }
    }
    return res;//failure
}

private static int search(int[] a, int val) {
    for(int i=0; i<a.length; i++){
        if (a[i] == val) return i;
    }
    return -1;
}

public static void main(String...args){
    int[] arr = {1,2,3,11,4,7,10};
    int[] res = isSum(arr, 21);
    System.out.println("res: {"+res[0]+","+res[1]+"}");
}

输出

水库：{3,6}

于 2013-08-21T04:07:00.393 回答
0 
public static boolean isSum(int[] arr,int val){
   int a,b=0;
   int c=0,d=0;
   boolean bol=false;
   for(a=0;a<arr.length;a++)
   {
       b=a+1;

   while(b<arr.length)
   {

       System.out.println(a+" "+b);

   if(arr[a]+arr[b]==val)
   {
       System.out.println(arr[a]+arr[b]);
   bol=true;
   c=a;
   d=b;
   break;
   }
   else
       b++;

   }

   }
   System.err.println(c+" "+d);
       return bol ;
    }
}
于 2013-08-21T06:34:21.337 回答
0

您必须将返回类型更改为（例如）一个数组，然后您必须捕获返回结果而不是直接返回它，如果它是真实的，则通过给定索引捕获值然后将它们返回到一个数组中，如果它是错误的返回一个空数组...测试返回数组的值，您将知道它是真还是假，并且如果它是真的，也会为您提供所需的值。

更新：

public static int[] isSum(int[] a, int val, int count, int index) {
int[] results = new int[2];
results[0] = -1;
results[1] = -1;

if (count == 0 && val == 0) {
    results[0] = 0;
    results[1] = 0;
    return results;
}
if (index >= a.length)
    return results;
else {

    if (isSum(a, val - a[index], count - 1, index + 1) == results) {
        if (isSum(a, val, count, index + 1) == results) {
            return results;
        } else {
            results[0] = val;
            results[1] = a[index + 1];
            return results;
        }
    } else {
        results[0] = val - a[index];
        results[1] = a[index + 1];
        return results;
    }

}
}
于 2013-08-21T04:45:15.180 回答