【Day33】1074.元素和为目标值的子矩阵数量

1074. 元素和为目标值的子矩阵数量

给出矩阵 matrix 和目标值 target,返回元素总和等于目标值的非空子矩阵的数量。

子矩阵 x1, y1, x2, y2 是满足 x1 <= x <= x2 且 y1 <= y <= y2 的所有单元 matrix[x][y] 的集合。

如果 (x1, y1, x2, y2) 和 (x1’, y1’, x2’, y2’) 两个子矩阵中部分坐标不同(如:x1 != x1’),那么这两个子矩阵也不同。

示例 1:

输入:matrix = [[0,1,0],[1,1,1],[0,1,0]], target = 0
输出:4
解释:四个只含 0 的 1x1 子矩阵。

示例 2:

输入:matrix = [[1,-1],[-1,1]], target = 0
输出:5
解释:两个 1x2 子矩阵,加上两个 2x1 子矩阵,再加上一个 2x2 子矩阵。

示例 3:

输入:matrix = [[904]], target = 0
输出:0

提示:

  • 1 <= matrix.length <= 100
  • 1 <= matrix[0].length <= 100
  • -1000 <= matrix[i] <= 1000
  • -10^8 <= target <= 10^8

题解:

二维前缀和的题目,使用哈希表来优化

#define HT_LENGTH 256

struct HashTable {
    int keys[HT_LENGTH];
    int vals[HT_LENGTH];

    HashTable() {
        this->clear();
    }

    void clear() {
        keys[0] = 0; vals[0] = 1;
        for (int i = 1;i < HT_LENGTH;i++) keys[i] = -1;
    }

    bool find(int key, int& ret) {
        uint32_t ikey = (uint32_t)key % HT_LENGTH;
        for (int i = 0;i < HT_LENGTH;i++) {
            if (keys[ikey] == -1) return false;
            if (keys[ikey] == key) {
                ret = vals[ikey];
                return true;
            }
            ikey ++;
            ikey = ikey == HT_LENGTH ? 0 : ikey;
        }
        return false;
    }

    void inc(int key) {
        uint32_t ikey = (uint32_t)key % HT_LENGTH;
        for (int i = 0;i < HT_LENGTH;i++) {
            if (keys[ikey] == -1) {
                keys[ikey] = key;
                vals[ikey] = 1;
                return;
            }
            if (keys[ikey] == key) {
                vals[ikey]++;
                return;
            }
            ikey ++;
            ikey = ikey == HT_LENGTH ? 0 : ikey;
        }
    }
};

class Solution {
private:
    HashTable ht;
public:
    int numSubmatrixSumTarget(vector>& matrix, int target) {
        int rprefix[100][101];
        int m = matrix.size(), n = matrix[0].size();
        int ret = 0;
        for (int i = 0;i < m;i++) {
            rprefix[i][0] = 0;
            for (int j = 1;j <= n;j ++) {
                rprefix[i][j] = rprefix[i][j - 1] + matrix[i][j - 1];
            }
        }

        for (int i = 1;i <= n;i++) {
            for (int j = i;j <= n;j++) {
                ht.clear();
                int cprefix = 0, val;
                for (int row = 0;row < m;row++) {
                    cprefix += rprefix[row][j] - rprefix[row][i - 1];
                    if (ht.find(cprefix - target, val)) ret += val;
                    ht.inc(cprefix);
                }
            }
        }
        return ret;
    }
};

   转载规则


《【Day33】1074.元素和为目标值的子矩阵数量》 Tyzhao 采用 知识共享署名 4.0 国际许可协议 进行许可。
 上一篇
【Day34】231. 2 的幂 【Day34】231. 2 的幂
231. 2 的幂给你一个整数 n,请你判断该整数是否是 2 的幂次方。如果是,返回 true ;否则,返回 false 。 如果存在一个整数 x 使得 n == 2x ,则认为 n 是 2 的幂次方。 示例 1: 输入:n = 1 输出:
2021-05-30
下一篇 
【Day32】477.汉明距离总和 【Day32】477.汉明距离总和
477. 汉明距离总和两个整数的 汉明距离 指的是这两个数字的二进制数对应位不同的数量。 计算一个数组中,任意两个数之间汉明距离的总和。 示例: 输入: 4, 14, 2 输出: 6 解释: 在二进制表示中,4表示为0100,14表示为
2021-05-28
  目录