如何编写递归布尔函数来查找数组是否可以从 i 到 length - 1 拆分为两段总和，以便它等于 diff

Question

public static boolean isSplitable(int[] arr, int diff, int i)

没有循环或辅助方法我需要检查 arr[i...arr.length - 1] 是否有等于 diff 的两部分总和例如我有： diff = 1, i = 2, arr = {3, 4, 1, 1, 2, 0, 1, 1, 3} 它 return 是真的，因为 {1, 1, 2, 0}(4) 减去 {1, 1, 3}(5) 的和等于 diff(1)。我试图想办法在没有循环的情况下对 arr 进行求和，我唯一想到的就是将它添加到 diff 但后来我失去了我原来的 diff 加上我不知道元素的数量所以我可以在我的 return 声明所以我现在没主意了。

Answer 1

我假设您的限制是没有循环，也没有使用库。您可能需要某种附加功能。此外，我假设差异检查应使用绝对值，即第一个或第二个总和较小并不重要，只要差异匹配（在您的示例中为 -1 或 1）。话虽如此，第一种方法可能如下所示：

import org.junit.jupiter.api.Test;

import static java.util.Arrays.copyOfRange;
import static org.junit.jupiter.api.Assertions.assertFalse;
import static org.junit.jupiter.api.Assertions.assertTrue;

public class RecursiveSplitTest {

  @Test
  public void testIsSplitable() {
    {
      int[] array = {3, 4, 1, 1, 2, 0, 1, 1, 3};
      assertTrue(isSplitable(array, 1, 2));
    }
    {
      int[] array = {3, 4, 1, 1, 1, 0, 4, 1, 3};
      assertTrue(isSplitable(array, 1, 4));
    }
    {
      int[] array = {3, 4, 1, 1, 1, 0, 4, 1, 3};
      assertFalse(isSplitable(array, 1, 7));
    }
    {
      int[] array = {3};
      assertFalse(isSplitable(array, 1, 1));
    }
  }

  public static boolean isSplitable(int[] array, int diff, int start) {
    if (start < 0 || start > array.length - 2) {
      System.out.println("Not possible due to initial parameters");
      return false;
    }

    return doSplitableRecursive(copyOfRange(array, start, array.length), diff, 0);
  }

  private static boolean doSplitableRecursive(int[] array, int diff, int start) {
    if (start + 1 >= array.length) {
      System.out.println("Could not find it");
      return false;
    }

    int[] left = copyOfRange(array, 0, start + 1);
    int[] right = copyOfRange(array, start + 1, array.length);

    int leftSum = sum(left, 0);
    int rightSum = sum(right, 0);
    System.out.println("leftSum: " + leftSum);
    System.out.println("rightSum: " + rightSum);

    if (leftSum + diff == rightSum || leftSum - diff == rightSum) {
      System.out.println("Found match for cut at start + " + (start + 1));
      return true;
    }

    return doSplitableRecursive(array, diff, start + 1);
  }

  private static int sum(int[] array, int current) {
    if (array.length == 0) {
      return current;
    }

    return sum(copyOfRange(array, 1, array.length), current + array[0]);
  }
}

关键是系统地将数组分成两部分，从头开始检查每部分的总和与差值。然后进一步切割一个索引，如果不匹配则重复该过程。最后，如果没有更多元素，则必须返回 false 退出。边缘有点粗糙。随意改进它并修复可能遗留的错误。打印语句用于调试目的。当然，有人会说 JUnit 和 java.util.Arrays 是库函数。如果需要，可以用一些额外的努力来替换这些。

如何编写递归布尔函数来查找数组是否可以从 i 到 length - 1 拆分为两段总和，以便它等于 diff

How to write a recursive boolean function to find if an array is splitable from i to length - 1 into a two segment sum so that it is equal to diff

java

arrays

recursion