假设我们有一个二维矩阵矩阵和一个值K,我们必须找到最长的矩形子矩阵,其总和与K相同。
所以,如果输入像
2 | 8 | -5 | 6 |
-7 | 7 | 8 | -3 |
11 | -14 | 4 | 3 |
-4 | 3 | 1 | 10 |
K = 9
那么输出将是左上点(1,0)和下右点(3,2)。
-7 | 7 | 8 |
11 | -14 | 4 |
-4 | 3 | 1 |
为了解决这个问题,我们将遵循以下步骤-
最大:= 100
定义一个函数sum_k(),它将使用一个数组arr,start,end,n,k,
定义一张映射
总和:= 0,最大长度:= 0
对于初始化i:= 0,当i <n时,更新(将i增加1),执行-
如果maximum_length <(i-map [sum-k]),则-
maximum_length:= i-map [sum-k]
开始:= map [sum-k] + 1
结束:=我
map [sum]:= i
最大长度:= i + 1
开始:= 0
结束:=我
sum:= sum + arr [i]
如果和等于k,则-
如果总和不在映射中,则-
如果(sum-k)在映射中,则-
当maximum_length不为0时返回true
从主要方法中,执行以下操作-
row:=垫子的行数,col:=垫子的列数
定义大小为行的数组临时文件。
定义一个数组final_point = {0,0,0,0}
maxArea:= -inf
对于initial left:= 0,当left <col时,更新(将left增加1),执行-
返回“未找到子矩阵”
对于初始化i:= 0,当i <行,更新(将i增加1)时,执行-
sum:= sum_k(温度,上,下,行,k)
区域:=(下-上+ 1)*(右-左+ 1)
如果sum为非零且maxArea <area,则-
temp [i]:= temp [i] + mat [i,right]
final_point [0]:=向上,final_point [1]:=向下
final_point [2]:=左,final_point [3]:=右
maxArea:=面积
用0填充温度
对于初始化right:= left,当right <col时,更新(将right增加1),执行-
如果final_point是[0,0,0,0]并且mat [0,0]不是k,则
显示左上角的点(final_point [0],final_point [2])
显示右下角的点(final_point [1],final_point [3])
显示垫子元素。
让我们看下面的实现以更好地理解-
#include <bits/stdc++.h> using namespace std; const int MAX = 100; bool sum_k(int arr[], int& start, int& end, int n, int k) { unordered_map<int, int> map; int sum = 0, maximum_length = 0; for (int i = 0; i < n; i++) { sum += arr[i]; if (sum == k) { maximum_length = i + 1; start = 0; end = i; } if (map.find(sum) == map.end()) map[sum] = i; if (map.find(sum - k) != map.end()) { if (maximum_length < (i - map[sum - k])) { maximum_length = i - map[sum - k]; start = map[sum - k] + 1; end = i; } } } return (maximum_length != 0); } void sum_zero(vector<vector<int>> &mat, int k) { int row = mat.size(); int col = mat[0].size(); int temp[row], area; bool sum; int up, down; vector<int> final_point = {0,0,0,0}; int maxArea = INT_MIN; for (int left = 0; left < col; left++) { memset(temp, 0, sizeof(temp)); for (int right = left; right < col; right++) { for (int i = 0; i < row; i++) temp[i] += mat[i][right]; sum = sum_k(temp, up, down, row, k); area = (down - up + 1) * (right - left + 1); if (sum && maxArea < area) { final_point[0] = up; final_point[1] = down; final_point[2] = left; final_point[3] = right; maxArea = area; } } } if (final_point[0] == 0 && final_point[1] == 0 && final_point[2] == 0 && final_point[3] == 0 && mat[0][0] != k) { cout << "No sub-matrix found"; return; } cout << "(Top, Left) Coordinate: " << "(" << final_point[0] << ", " << final_point[2] << ")" << endl; cout << "(Bottom, Right) Coordinate: " << "(" << final_point[1] << ", " << final_point[3] << ")" << endl; for (int j = final_point[0]; j <= final_point[1]; j++) { for (int i = final_point[2]; i <= final_point[3]; i++) cout << mat[j][i] << " "; cout << endl; } } main(){ vector<vector<int>> v = { { 2, 8, -5, 6 }, { -7, 7, 8, -3 }, { 11, -14, 4, 3 }, { -4, 3, 1, 10 }}; sum_zero(v, 9); }
{{ 2, 8, -5, 6 }, { -7, 7, 8, -3 }, { 11, -14, 4, 3 }, { -4, 3, 1, 10 }}, 9
输出结果
(Top, Left) Coordinate: (1, 0) (Bottom, Right) Coordinate: (3, 2) -7 7 8 11 -14 4 -4 3 1