一、题目

你的面前有一堵矩形的、由 n 行砖块组成的砖墙。这些砖块高度相同（也就是一个单位高）但是宽度不同。每一行砖块的宽度之和应该相等。

你现在要画一条 自顶向下 的、穿过 最少 砖块的垂线。如果你画的线只是从砖块的边缘经过，就不算穿过这块砖。你不能沿着墙的两个垂直边缘之一画线，这样显然是没有穿过一块砖的。

给你一个二维数组 wall ，该数组包含这堵墙的相关信息。其中，wall[i] 是一个代表从左至右每块砖的宽度的数组。你需要找出怎样画才能使这条线 穿过的砖块数量最少 ，并且返回 穿过的砖块数量 。

点击查看原题

二、思路

最开始看到本题，潜意识认为是动态规划的题，经过仔细思考后，发现无法化简成为子问题，其实就是到达每一行后，需要对该间隙是否存在砖头做判断。
由于给出的数据每块砖的长度，最开始的思路是：
选定一个间隙i，每次都向下一行判断是否有间隙可以穿过，那么问题就在于如何建立数据，能够时间O(1)地查询是否存在间隙。
本来想的是能否用前缀和的形式，将wall中的数据改为前缀和，通过判断即可。（但此方法需要先执行一遍时间遍历改变数据，又需要用时间来确认每个间隙穿过的砖头数量）。

如上所述的思路有些问题，这样空间复杂度确实低，但时间就浪费很多了，那采取空间换时间的方式，记录下每个间隙穿过间隙的数量即可。只需要遍历wall，根据每一行，使用前缀和来进行判断是否间隙。

三、代码

class Solution {
    public int leastBricks(List<List<Integer>> wall) {
        Map<Long, Integer> map = new HashMap();
        for (List<Integer> single : wall) {
            long sum = 0;
            for (int i = 0; i < single.size() - 1; i++) {
                sum += single.get(i);
                map.put(sum, map.getOrDefault(sum, 0) + 1);    // 和下面注释的几行功能一样
                // if (map.containsKey(sum)) {
                //     map.put(sum, map.get(sum) + 1);
                // } else {
                //     map.put(sum, 1);
                // }
            }
        }
        int ans = 0;
        // 找到穿过间隙最多的
        for (Map.Entry<Long, Integer> entry : map.entrySet()) {
            ans = Math.max(ans, entry.getValue());
        }
        return wall.size() - ans;
    }
}

时间复杂度为，空间复杂度为。