Daily LeetCode – day0108 0805. Split Array With Same Average

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

// 0805. Split Array With Same Average
class Solution {
    public boolean splitArraySameAverage(int[] nums) {
        int n = nums.length;
        if (n == 1) return false;
        int mid = n / 2;
        int sum = 0;
        for (int num : nums) {
            sum += num;
        }
        for (int i = 0; i < n; ++i) {
            nums[i] = nums[i] * n - sum;
        }
        int leftCombinations = 1 << mid;
        int rightCombinations = 1 << n - mid;
        Set<Integer> leftSums = new HashSet<>();
        for (int i = 1; i < leftCombinations; ++i) {
            int total = 0;
            for (int j = 0; j < mid; ++j) {
                if ((i & (1 << j)) != 0) {
                    total += nums[j];
                }
            }
            if (total == 0) return true;
            leftSums.add(total);
        }
        for (int i = 1; i < rightCombinations - 1; ++i) {
            int total = 0;
            for (int j = mid; j < n; ++j) {
                if ((i & (1 << j - mid)) != 0) {
                    total += nums[j];
                }
            }
            if (total == 0) return true;
            if (leftSums.contains(total * -1)) return true;
        }
        return false;
    }
}

学习笔记：
这道是一道超级困难题。
如果使用深度优先搜索，需要2的30次方的时间，太离谱了。
所以我们要用折半搜索，先搜2的15次方，再搜2的15次方，然后拿左半去右半里面找有没有相反的数字。