题解 | 小苯的美丽区间

分享一下这道题的题解～

这道题目的是找到有多少个子数组的区间和是一个美丽值，再求它们的累加和

所以我们可以使用前缀和找到子数组的区间和：PreSum[i] - PreSum[j]

美丽值是指2的指数次方，我们可以提前记录一下

所以，PreSum[i] - PreSum[j] = 2^x

PreSum[i] - 2^x = PreSum[j]

PreSum[j]我们可以在遍历的时候记录一下出现的次数，然后遍历x，找到有多少可能的等式存在，然后和x相乘，累加到答案中。

import java.util.Scanner;
import java.util.Map;
import java.util.HashMap;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int T = in.nextInt();
        long[] exp = new long[62];
        exp[0] = 1;
        for (int i = 1; i < 62; i++) {
            exp[i] = exp[i-1] * 2;
        }
        for (int c = 0; c < T; c++) {
            int n = in.nextInt();
            long[] a = new long[n+1];
            long ans = 0;
            for (int i = 1; i <= n; i++) {
                a[i] = in.nextLong() + a[i-1];
            }
            Map<Long, Integer> map = new HashMap<>(n+3);
            map.put((long) 0, 1);
            for (int i = 1; i <= n; i++) {
                for (int j = 0; j < exp.length; j++) {
                    // find a[i] - x = exp[j]
                    if (map.containsKey(a[i] - exp[j])) {
                        ans += map.get(a[i] - exp[j]) * j;
                    }
                }
                if (map.containsKey(a[i])) {
                    map.put(a[i], map.get(a[i]) + 1);
                } else {
                    map.put(a[i], 1);
                }
            }
            System.out.println(ans);
        }
    }
}