【算法挨揍日记】day16——525. 连续数组、1314. 矩阵区域和

水深无声 2024-02-22 07:14 11阅读 0赞

![33ebb693c51541458b99d2e3300e95b4.png][]

## 525. 连续数组 ##

[525. 连续数组][525.]

### 题目描述： ###

给定一个二进制数组 `nums` , 找到含有相同数量的 `0` 和 `1` 的最长连续子数组，并返回该子数组的长度。

![a5c39dfa6e1842759e575b5316d979bd.png][]

### 解题思路： ###

本题的元素只有0和1，根据题目意思，我们可以把题目看成找一段最长的子区间使得区间的0

和1的数量相同，我们可以对其优化将所有的0变成-1，这样这段区间的和就为0

也就是转化为在【0，i-1】这个区间内最长的和为0的子数组

我们依旧可以利用哈希表hash，我们还得处理一下默认前缀和为0的时候等于-1的时候

长度的计算：

![706694a5d4564e589387dbb225071ab0.png][]

### 解题思路： ###

class Solution {
    public:
        int findMaxLength(vector<int>& nums) {
            unordered_map<int,int>hash;
            hash[0]=-1;
            int ret=0,sum=0;
            for(int i=0;i<nums.size();i++)
            {
                sum+=nums[i]==0?-1:1;
                if(hash.count(sum))ret=max(ret,i-hash[sum]);
                else hash[sum]=i;
            }
            return ret;
        }
    };

--------------------

## 1314. 矩阵区域和 ##

[1314. 矩阵区域和][1314.]

### 题目描述： ###

给你一个 `m x n` 的矩阵 `mat` 和一个整数 `k` ，请你返回一个矩阵 `answer` ，其中每个 `answer[i][j]` 是所有满足下述条件的元素 `mat[r][c]` 的和：

*  `i - k <= r <= i + k,`
 *  `j - k <= c <= j + k` 且
 *  `(r, c)` 在矩阵内。

### ![d211862361944ab18e28e51cdd691599.png][] ###

### 解题思路： ###

本题我们还是使用前缀和+哈希表，不过是二维前缀和

因为本题的计算的下标的范围可能会越界，因此我们可以min和max函数就行解决，这里的+1是因为需要进行下标匹配，下标匹配下面会讲;

![b4a75890e17b4f2e8cbd5c15e6274ebe.png][]

有个细节需要注意就是：

我们的mat数组是从0开始的，而我们的前缀和数组dp是从1开始，而我们返回的数组ans是从0开始的

因为力扣进行结果判断的时候需要从0开始，不然本题更加简单  
![da77d3e1c5cd4414849c776f512f864b.png][]

### 解题代码： ###

class Solution {
    public:
        vector<vector<int>> matrixBlockSum(vector<vector<int>>& mat, int k) {
            int n=mat.size();
            int m=mat[0].size();
            vector<vector<int>> dp(n+1,vector<int>(m+1));
            for(int i=1;i<=n;i++)
                for(int j=1;j<=m;j++)
                    dp[i][j]=dp[i-1][j]+dp[i][j-1]-dp[i-1][j-1]+mat[i-1][j-1];
            vector<vector<int>> ans(n,vector<int>(m));
            for(int i=0;i<n;i++)
            {
                for(int j=0;j<m;j++)
                {
                    int x1=max(0,i-k)+1;
                    int y1=max(0,j-k)+1;
                    int x2=min(n-1,i+k)+1;
                    int y2=min(m-1,j+k)+1;
                    ans[i][j]=dp[x2][y2]-dp[x2][y1-1]-dp[x1-1][y2]+dp[x1-1][y1-1];
                }
            }
            return ans;
        }
    };

[33ebb693c51541458b99d2e3300e95b4.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/22/b4b5f11f87fd41b09f583fef161115c3.png
[525.]: https://leetcode.cn/problems/contiguous-array/
[a5c39dfa6e1842759e575b5316d979bd.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/22/df4d7e25f4474b2da3861daf0fa5cac8.png
[706694a5d4564e589387dbb225071ab0.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/22/e30f4ccac9624701a630c89e55b2ca5d.png
[1314.]: https://leetcode.cn/problems/matrix-block-sum/
[d211862361944ab18e28e51cdd691599.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/22/1cf81d264d9f42319396143408e06303.png
[b4a75890e17b4f2e8cbd5c15e6274ebe.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/22/cab5f173700241b9b8be3c0b009bb754.png
[da77d3e1c5cd4414849c776f512f864b.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/22/37617f2e068644489973bba0f3c82f0e.png