找到方程的最小匹配值

Question

我有一个整数数组，例如 [1, 2, 3, 6, 67]

我有一个等式：

a*x+b*y=z,

我可以使用这个方程中的数组值来替换x和y，通过一些数组位置说arr[i]，arr[j] i和j可以不同或相同。

所以它看起来像这样：

a*arr[i] + b*arr[j] = z;

现在我有了另一个数组

Zarr = [1, 4, 30, 7, 88]

任务是找到 a 和 b 的值，使得

a*arr[i] + b*arr[j] = Zarr[k]

，其中 k 是 Zarr 的索引位置。

计算完a和b后，我需要得到总和

(a + b)

并将其存储在结果中，条件是总和

(a+b)

应该是最小值。

我还有 1 个限制，如果 a+b 之和大于输入变量

Z_MAX

，则将该索引的结果设置为 -1；

示例：

so for arr =  [1, 2, 3, 6, 67]
Zarr = [1, 4, 30, 7, 88]
Z_MAX = 5

结果是

[1,2,5,2,-1]

说明：

Zarr[0] = 1
i=0, j=0
a=1, b=0
sum = a+b = 1
Eq = 1*1 + 0*1 = 1

Zarr[1] = 4
i=1, j=1
a=1, b=1
sum = a+b = 2
Eq = 1*2 + 1*2 = 4

Zarr[2] = 30
i=3, j=3
a=5, b=0
sum = a+b = 5
Eq = 5*6 + 0*6 = 30

Zarr[3] = 7
i=0, j=3
a=1, b=1
sum = a+b = 2
Eq = 1*1 + 1*6 = 7

Zarr[4] = 88
It's not possible to find a and b whose sum to be less than or equal to Z_MAX, so -1

Finally result = [1,2,5,2,-1]

这是我的代码，使用暴力方法：

public static void main(String[] args) {
    int[] a = solve(new int[]{1, 2, 3, 6, 67}, new int[]{1, 4, 30, 7, 88}, 5);
    System.out.println(Arrays.toString(a));//1,2,5,2,-1
}


public static int[] solve(int[] arr, int[] zArr, int Z_MAX) {
    int n = arr.length;
    int[] result = new int[zArr.length];
    for(int i=0; i<zArr.length; i++) {
        result[i] = Integer.MAX_VALUE;
    }
    for (int p = 0; p < zArr.length; p++) {
      int z = zArr[p];
      
      for(int i=0; i<n; i++) {
          for(int j=0; j<n;j++) {
              
              for (int a = 0; a <= Z_MAX; a++) {
                for (int b = 0; b <= Z_MAX; b++) {
                  if (a * arr[i] + b * arr[j] == z) {
                    result[p] = Math.min(result[p], a + b);
                    break;
                  }
                }
              }
          }
      }
      if (result[p] > Z_MAX) {
        result[p] = -1;
      }
    }
    return result;
}

限制：

array size is of range 1 to 1000
array element values in range 1 to 10^7
Z_MAX is 1 to 20
zArr size is 1 to 20
zArr element values in range 1 to 10^9

解决这个问题的正确方法是什么，如何降低时间复杂度？

Answer 1

你的算法是 O(n^2 * z_max^2)。但是使用 2 个指针，假设 arr 已经排序，则可以将其降低到 O(n * z_max^2)，否则为 O(n log n + n^2 * z_max^2)。

// expects ordered arr
public static int solve(int[] arr, int z, int Z_MAX) {
    // check special case where a or b is 0
    int res = Z_MAX + 1;
    for (int i = arr.length - 1; i >= 0 && z / arr[i] <= Z_MAX; i--) {
        if (z % arr[i] == 0) {
            res = z / arr[i];
            break;
        }
    }
    // now check other cases in order
    for (int sum = 2; sum < res; sum++) {
        for (int a = 1; a < sum; a++) {
            int b = sum - a;
            int j = arr.length - 1;
            for (int i = 0; i < arr.length; i++) {
                // this is the key, the j pointer going left as needed
                while (j >= 0 && a * arr[i] + b * arr[j] > z)
                    j--;
                if (j < 0)
                    break;
                if (a * arr[i] + b * arr[j] == z)
                    return sum;
            }
        }
    }
    return res <= Z_MAX ? res : -1;
}