折半搜索

概述

折半搜索（meet-in-the-middle），虽然听起来有点像二分查找，但是其实是两种不同的算法。一般针对数组元素组合的暴力搜索，复杂度会来到 O(2^n)，稍微有点数据量就容易TLE。而折半搜索则是一种取巧的方式，一次只爆搜一半的数据，爆搜两次，然后将两次爆搜的结果组合起来，就可以提升很多效率。不过复杂度依然是指数级别的。

---

例题

LeetCode 805. 数组的均值分割

给定你一个整数数组 nums

我们要将 nums 数组中的每个元素移动到 A 数组 或者 B 数组中，使得 A 数组和 B 数组不为空，并且 average(A) == average(B) 。

如果可以完成则返回true ， 否则返回 false 。

注意：对于数组 arr , average(arr) 是 arr 的所有元素的和除以 arr 长度。

提示：1 <= nums.length <= 30

示例 1：

输入: nums = [1,2,3,4,5,6,7,8]
输出: true
解释: 我们可以将数组分割为 [1,4,5,8] 和 [2,3,6,7], 他们的平均值都是4.5。

示例 2：

输入: nums = [3,1]
输出: false

---

题解

分割后的两个数组的平均数相同，那么把它们和回去，平均数肯定不变，所以两个数组的平均数等于原数组的平均数。所以我们只需要判断原数组是否存在一个平均数和原数组的平均数相等的非空子数组就行了。

本题数组最长长度会有30，如果直接二进制暴力枚举的话，需要枚举 2^30 次，指定会TLE。所以就可以使用折半搜索，先搜索前半部分，然后把搜索结果存进哈希表里，然后再搜剩下一半。在搜剩下一半时，每枚举到一种组合，就再枚举它和前半部分组合后的组合的长度和这个长度对应的理论元素总和，然后去哈希表中查找这个理论总和是否真实存在，如果存在就说明我们找到了可行解，返回 true 即可。这样我们最多只需要枚举两个 2^15 就行，数量级一下子就下来了。

代码：

class Solution {
public:
    bool splitArraySameAverage(vector<int>& nums) {
        int n = nums.size();
        int sum = accumulate(nums.begin(), nums.end(), 0);
        int m = n / 2;
        unordered_map<int, unordered_set<int>> map;/* cnt,sum */
        for (int i = 0; i < (1 << m); i++) {
            int temp = i;
            int tsum = 0, tcnt = 0;
            int idx = 0;
            while (temp > 0) {
                if (temp & 1) {
                    tsum += nums[idx];
                    tcnt++;
                }
                idx++;
                temp >>= 1;
            }
            map[tsum].insert(tcnt);
        }
        int r = n - m;
        for (int i = 0; i < (1 << r); i++) {
            int temp = i;
            int tsum = 0, tcnt = 0;
            int idx = 0;
            while (temp > 0) {
                if (temp & 1) {
                    tsum += nums[m + idx];
                    tcnt++;
                }
                idx++;
                temp >>= 1;
            }
            for (int j = max(1,tcnt); j < n; j++) {
                if (j * sum % n != 0) continue;
                int t = j * sum / n;
                if (map[t - tsum].count(j - tcnt)) return true;
            }
        }
        return false;
    }
};

---

有的没的

没事听点歌（金玟岐 - 岁月神偷）