线性组合匹配问题优化求解：如何降低时间复杂度？

给定整数数组arr（示例：[1, 2, 3, 6, 67]），需满足方程 a*x + b*y = z，其中x、y取自arr的元素（可使用同一位置的元素），即 a*arr[i] + b*arr[j] = z。另有目标数组Zarr（示例：[1, 4, 30, 7, 88]），针对Zarr中每个元素Zarr[k]，需找到整数a、b使等式成立，且a+b的和最小；若最小和超过输入变量Z_MAX，则对应结果设为-1。

示例输入输出 #

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

结果为 [1,2,5,2,-1]

原暴力实现代码（Java） #

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;
}

约束条件 #

• 数组arr长度范围：1~1000
• 数组arr元素值范围：1~10^7
• Z_MAX范围：1~20
• 数组Zarr长度范围：1~20
• 数组Zarr元素值范围：1~10^9

核心优化思路 #

原暴力法时间复杂度为O(M*N²*Z_MAX²)（M为Zarr长度，N为arr长度），当N=1000时，仅N²就达到1e6，结合Z_MAX=20的平方400，总运算量会突破8e9，完全无法高效运行。优化方向如下：

1. 优先按最小sum遍历，提前终止：从sum=1开始遍历可能的a+b值，一旦找到符合条件的sum，直接停止当前z的所有计算，避免无效遍历。
2. 哈希表快速查询元素：将arr存入哈希集合，检查元素是否存在的时间从O(N)降至O(1)。
3. 数学推导替代暴力枚举：对每个(a,b)组合，通过计算直接推导y的可能值，而非遍历所有y元素。
4. 去重arr减少重复计算：去除arr中的重复元素，减少遍历次数。

优化后的Java代码 #

import java.util.Arrays;
import java.util.HashSet;
import java.util.Set;

public class Solution {
    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) {
        // 去重并存入哈希集合，快速查询元素存在性
        Set<Integer> arrSet = new HashSet<>();
        for (int num : arr) {
            arrSet.add(num);
        }
        int m = zArr.length;
        int[] result = new int[m];

        for (int p = 0; p < m; p++) {
            int z = zArr[p];
            int minSum = -1;

            // 按sum从小到大遍历，找到第一个符合条件的sum就停止
            for (int sum = 1; sum <= Z_MAX; sum++) {
                // 遍历所有可能的(a,b)组合，满足a+b=sum
                for (int a = 0; a <= sum; a++) {
                    int b = sum - a;
                    if (a > Z_MAX || b > Z_MAX) {
                        continue;
                    }

                    boolean found = false;
                    if (a == 0) {
                        // 检查是否存在y使得b*y=z
                        if (z % b != 0) continue;
                        int y = z / b;
                        if (y >= 1 && arrSet.contains(y)) found = true;
                    } else if (b == 0) {
                        // 检查是否存在x使得a*x=z
                        if (z % a != 0) continue;
                        int x = z / a;
                        if (x >= 1 && arrSet.contains(x)) found = true;
                    } else {
                        // 遍历x，计算对应的y并检查是否在集合中
                        for (int x : arr) {
                            long rem = z - (long)a * x;
                            if (rem < 0 || rem % b != 0) continue;
                            int y = (int)(rem / b);
                            if (y >= 1 && arrSet.contains(y)) {
                                found = true;
                                break;
                            }
                        }
                    }

                    if (found) {
                        minSum = sum;
                        break;
                    }
                }
                if (minSum != -1) break;
            }
            result[p] = minSum;
        }
        return result;
    }
}

时间复杂度对比 #

优化后的时间复杂度为O(M*Z_MAX²*N)，但实际运行中因为提前终止遍历，运算量远低于理论值：

• 当Z_MAX=20，M=20，N=1000时，总运算量约为4.2e6，相比原暴力法的8e9，效率提升了近2000倍。
• 哈希表的查询操作进一步减少了内层循环的耗时，去重操作也能有效降低N的实际遍历规模。

内容的提问来源于stack exchange，提问作者Learner