如何找到元组数量，使其总和等于或小于给定数字？

Question

如何找到元组数量，使其总和等于或小于给定数字？

4

我正在设计一个算法来查找元组数量，这些元组的总和等于或小于给定的数字。我知道使用LinkedList解决它的其他方法，因此不寻求那种解决方案。我只想遍历数组并计算满足关系的可能匹配项。到目前为止，我得出了以下结果：

public static int numberOfPairs(int[] a, int k ){

    int len = a.length;

    if (len == 0){

      return -1;
    }

    Arrays.sort(a);
    int count  = 0, left = 0, right = len -1; 

    while( left < right ){

        if ( a[left] + a[right] <= k  ){

            // System.out.println(a[left] + "\t" + a[right]);
            count++; 

            /*may be the same numbers will also satisfy the relation*/
            if ( a[left] + a[left+1] <= k) {

                count ++;
                // System.out.println(a[left] + "\t"+a[left+1]);
            }

            /*now, use iteration to traverse the same elements*/
            while (a[left] == a[left+1] && left < len-1 ){

              left++;
            }

            /*may be the same numbers will also satisfy the relation*/
            if ( a[right] + a[right-1] <= k) {

                count ++;
                // System.out.println(a[right] +"\t"+ a[right-1]);
            }

            /*now, use iteration to traverse 
            the same elements*/
            while ( a[right] == a[right-1] && right >1 ){

              right-- ; 
            }
        }

        // traverse through the array
        left++;
        right--;
    }

    return count; 
}

这不提供正确的解决方案。比如，如果我传入以下数组和数字：

int [] arr = { 3, 3, -1, 4, 2,5, 5, 1};
System.out.println(numberOfPairs(arr, 8));

正确的解决方案将是以下15对：

{ 
        {-1,1},  {-1,2} ,  {3,-1}, {-1,4 }, {-1,5}, 
        {2,1},{3,1 },{4,1}, { 5,1},
        {3,2 },{4,2}, {2,5 }, 
        {3,4 } ,  {3,5 },   
        {3,3}

我该如何提高我的代码质量？谢谢。

注意：我使用链表解决问题的另一种方法如下：

public static int numberOfPairs10(int[] arr, int sum){

    /*1.can be the same values of i 
     2. can be the same valus of j for the same i*/
    List<Integer> li = new ArrayList<Integer>();
    List<Integer> lj;
    int count = 0; 

    for ( int i =0; i < arr.length -1 ; i++){

        if (li.contains(arr[i]) )
            continue; 

        lj =  new ArrayList<Integer>();
        for (int j = i+1; j < arr.length; j++){

            if (lj.contains(arr[j]))
                continue;

            // if ( arr[i]+ arr[j] <= sum){
            if ( arr[i]+ arr[j] == sum){

                count++;
                lj.add(arr[j]);
            }
        }

        li.add(arr[i]);
    }

    return count;
}

- Arefe

1

为避免您示例中出现的(3,5)重复，您将需要存储一些数据来确定哪些组合已经被计算过，我认为这是无法避免的。 - user3284549

我不想要一个需要额外存储的解决方案，但是排序是可以的。 - Arefe

2个回答

2

如果您不太关心性能，那么您可以找到所有唯一的组合，然后根据条件进行过滤。例如，使用Java 8流：

public int numberOfPairs(int[] values, int maxVal) {
    return IntStream.range(0, values.length)
        .flatMap(i1 -> IntStream.range(i1 + 1, values.length)
            .map(i2 -> Arrays.asList(values[i1], values[i2])))
        .distinct().filter(l -> l.stream().sum() <= maxVal).count();
}

- sprinter

我只了解Java 8的基础知识，但我很感激这个答案。你能否提供此解决方案所需的导入列表？ - Arefe

1

java.utils.stream.Stream 和 java.utils.stream.IntStream - sprinter

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- gilchris · Accepted Answer

这是仅使用的测试

int [] arr = { 3, 3, -1, 4, 2,5, 5, 1};
numberOfPairs(arr, 8);

这里是代码

public static int numberOfPairs(int[] a, int k ) {
    int len = a.length;
    int counter = 0;
    boolean isCheckedLeft = false;
    boolean isCheckedRight = false;
    int i, j, h;

    Arrays.sort(a);
    for (i = 0; i < len; i++) {

        isCheckedLeft = false;
        for (j = i - 1; j >= 0; j--) {
            if (a[i] == a[j]) {
                isCheckedLeft = true;
                break;
            }
        }
        if (isCheckedLeft) {
            continue;
        }

        for (j = i + 1; j < len; j++) {

            isCheckedRight = false;
            for (h = j - 1; h > i; h--) {
                if (a[j] == a[h]) {
                    isCheckedRight = true;
                    break;
                }
            }
            if (isCheckedRight) {
                continue;
            }

            System.out.print("("+a[i]+", "+a[j]+") ");
            if (a[i] + a[j] <= k) {
                counter++;
            }
        }
    }
    return counter;
}