【算法学习笔记】28：Meet In The Middle优化

1 定义

当一个问题使用时间复杂度为 $O (e x p r (n))$ 会超时或者爆内存时，如果它存在这样的性质，可以分别对折半后的前后两个 $\frac{n}{2}$ 的子问题进行搜索，并能根据这两个子问题的解，在 $< O (e x p r (n))$ 的时间内得到原问题的解时，就可以分别处理两个折半后的子问题，然后用两个子问题计算原问题的结果，称为Meet In The Middle。

这样就把时间复杂度从 $O (e x p r (n))$ 变成了 $\cdot expr(\frac{n}{2}))$ ，可能就过了，往往用在比较暴力的问题上，数据范围比较小可以暴力但却不能纯暴力通过。

2 例题

2.1 LC1755. 最接近目标值的子序列和

由于子序列就是这个序列里每个元素存在或者不存在（二元性问题），并且数据范围是<=40 < bits of ULL，所以可以用ULL当bitset来存每个元素pick或者not pick。

然后就可以暴力里找出 $2^n$ 种选法的子序列和，放在sums里，其中 $s u m s [ma s k]$ 就是把 $ma s k$ 的每个为1的比特 $i$ 拆出来，所有满足条件的 $i$ 对应的 $n u m s [i]$ 的加和。

这个过程可以稍微优化一下，考虑到加法结合律a + b + c = (a + b) + c，只要算过(a + b)了只要+c就能算出a + b + c。

比如一共n位， $i$ 从低位（1<<0这一位）到高位（1<<(n-1)这一位），每次计算 $i$ 这一位为1，并且 $> i$ 的位置全都为0的情况，此时 $< i$ 的所有情况的加和都已经算出来过了，只要遍历一遍这些 $sub_mask$ ，把这些已经算好的 $sums[sub_mask]$ 加上 $n u m s [i]$ 就是 $sums[sub_mask | 1 << i]$ 了。

得到所有 $s u m s$ 之后，只要排序在进行二分查找就可以找到最接近目标值的子序列和了：

class Solution {
public:int minAbsDifference(vector<int>& nums, int goal) {int n = nums.size();vector<int> sums(1ULL << n, 0);for (int i = 0; i < n; i ++ ){auto cur_bit = 1ULL << i;for (auto sub_mask = 0ULL; sub_mask < cur_bit; sub_mask ++ ){sums[cur_bit | sub_mask] = sums[sub_mask] + nums[i];}}sort(sums.begin(), sums.end());int l = 0, r = sums.size() - 1;while (l < r){int mid = l + r + 1 >> 1;if (sums[mid] <= goal) l = mid;else r = mid - 1;}int res = abs(goal - sums[l]);if (l + 1 < sums.size()) res = min(res, abs(goal - sums[l + 1]));return res;}
};

但是这样对 $n <= 40$ 这个范围还是过于暴力了，数据量大点就过不了了。

考虑到把区间拆成左右两半的话，目标子序列要么全存在于左侧或者右侧区间（子问题），要么是左区间的某个子序列和右区间的某个子序列拼在一起，对应sums也是两者的sums加和（可以从两个子问题的结果得到）。

得到的方式可以用双指针，对于左右排好序的sums，两个指针分别指向左区间开头和右区间末尾，每次 $< g o a l$ 就把左侧区间指针往右移动，每次 $> g o a l$ 就把右侧区间指针往左移动，这样扫一遍就能在 $\cdot 2^{\frac{n}{2}})$ 里从两个子问题得到结果。

又知，左右两个子区间排序的时间复杂度是 $\frac{n}{2} \cdot log(\frac{n}{2})$ ，这样所有的部分都没有对两个子问题进行暴力计算sums花的时间复杂度（一共 $\cdot 2^{\frac{n}{2}}$ ）大。

class Solution {
public:vector<int> make_sums(span<int> nums){int n = nums.size();vector<int> sums(1ULL << n, 0);for (int i = 0; i < n; i ++ ){auto cur_bit = 1ULL << i;for (auto sub_mask = 0; sub_mask < cur_bit; sub_mask ++ ){sums[cur_bit | sub_mask] = sums[sub_mask] + nums[i];}}sort(sums.begin(), sums.end());return sums;}int find_ans(span<int> sums, int goal){int l = 0, r = sums.size() - 1;while (l < r){int mid = l + r + 1 >> 1;if (sums[mid] <= goal) l = mid;else r = mid - 1;}int res = abs(sums[l] - goal);if (l + 1 < sums.size()) res = min(res, abs(sums[l + 1] - goal));return res;}int minAbsDifference(vector<int>& nums, int goal) {int n = nums.size();span<int> fullspan(nums);int ln = n >> 1;auto lsums = make_sums(fullspan.subspan(0, ln));int rn = n - ln;auto rsums = make_sums(fullspan.subspan(ln, rn));int res = min(find_ans(lsums, goal), find_ans(rsums, goal));int i = 0, j = rsums.size() - 1;while (i < lsums.size() && j >= 0){int val = lsums[i] + rsums[j];res = min(res, abs(val - goal));if (val < goal) i ++ ;else if (val == goal) return 0;else j -- ;}return res;}
};