1. 寻找数组的中心下标 2. 除了自身以外数组的乘积
3. 和为K的子数组 4. 和可被K整除的子数组
5. 连续数组 6. 搜索二维矩阵 7. 矩阵区域和⭐
1. 寻找数组的中心下标
LCR 012. 寻找数组的中心下标
https://leetcode.cn/problems/tvdfij/
给你一个整数数组 nums ，请计算数组的 中心下标 。
数组 中心下标 是数组的一个下标，其左侧所有元素相加的和等于右侧所有元素相加的和。
如果中心下标位于数组最左端，那么左侧数之和视为 0 ，因为在下标的左侧不存在元素。这一点对于中心下标位于数组最右端同样适用。
如果数组有多个中心下标，应该返回 最靠近左边 的那一个。如果数组不存在中心下标，返回 -1 。
class Solution {
public:
int pivotIndex(vector<int>& nums) {
int total = 0;
for (int num : nums) {
total += num;
}
int sum = 0;
for (int i = 0; i < nums.size(); ++i) {
sum += nums[i];
if (total – sum == sum – nums[i]) {
return i;
}
}
return -1;
}
};
思路：前缀和 + 后缀和
2. 除了自身以外数组的乘积
238. 除了自身以外数组的乘积https://leetcode.cn/problems/product-of-array-except-self/
给你一个整数数组 nums，返回 数组 answer ，其中 answer[i] 等于 nums 中除了 nums[i] 之外其余各元素的乘积 。
题目数据 保证 数组 nums之中任意元素的全部前缀元素和后缀的乘积都在 32 位 整数范围内。
请 不要使用除法，且在 O(n) 时间复杂度内完成此题。
写法一：前缀和后缀
class Solution {
public:
vector<int> productExceptSelf(vector<int>& nums) {
vector<int> prenums,lastnums,result;
int i=1,x=1;
for(auto& e:nums)
{
i*=e;
prenums.emplace_back(i);
}
for(int j=nums.size()-1;j>=0;–j)
{
x*=nums[j];
lastnums.emplace_back(x);
}
int add;
for(int q=0;q<nums.size();q++)
{
if(q==0)
add=lastnums[nums.size()-2];
else if(q==nums.size()-1)
add=prenums[nums.size()-2];
else
add=prenums[q-1]*lastnums[nums.size()-q-2];
result.emplace_back(add);
}
return result;
}
};
写法二：前缀和后缀
class Solution {
public:
vector<int> productExceptSelf(vector<int>& nums) {
int len = nums.size();
if (len == 0) return {};
vector<int> ans(len, 1);
ans[0] = 1;
int tmp = 1;
for (int i = 1; i < len; i++) {
ans[i] = ans[i – 1] * nums[i – 1];
}
for (int i = len – 2; i >= 0; i–) {
tmp *= nums[i + 1];
ans[i] *= tmp;
}
return ans;
}
};
3. 和为K的子数组
560. 和为 K 的子数组https://leetcode.cn/problems/subarray-sum-equals-k/
给你一个整数数组 nums 和一个整数 k ，请你统计并返回 该数组中和为 k 的子数组的个数 。
子数组是数组中元素的连续非空序列。
class Solution {
public:
int subarraySum(vector<int>& nums, int k) {
unordered_map<int,int> kv={{0,1}};
int add=0,i=0;
for(auto& e:nums)
{
add+=e;
auto it=kv.find(add-k);
if(it!=kv.end())
i+=it->second;
kv[add]++;
}
return i;
}
};
4. 和可被K整除的子数组
974. 和可被 K 整除的子数组https://leetcode.cn/problems/subarray-sums-divisible-by-k/
给定一个整数数组 nums 和一个整数 k ，返回其中元素之和可被 k 整除的非空 子数组 的数目。
子数组 是数组中 连续 的部分。
class Solution {
public:
int subarraysDivByK(vector<int>& nums, int k) {
unordered_map<int,int> hash={{0,1}};
int sum=0,r,count=0;
for(auto& e:nums)
{
sum+=e;
r=(sum%k+k)%k;
if(hash.count(r))
count+=hash[r];
hash[r]++;
}
return count;
}
};
5. 连续数组
525. 连续数组https://leetcode.cn/problems/contiguous-array/
给定一个二进制数组 nums , 找到含有相同数量的 0 和 1 的最长连续子数组，并返回该子数组的长度。
写法一：哈希+前缀和
class Solution {
public:
int findMaxLength(vector<int>& nums) {
unordered_map<int, int> m = {{0,-1}};
int cur = 0, ans = 0;
for(int i = 0; i < nums.size(); ++i)
{
nums[i] == 0? –cur : ++cur;
if(m.count(cur))
ans = max(ans, i – m[cur]);
else
m[cur] = i;
}
return ans;
}
};
写法二：哈希+dp
class Solution
{
public:
int findMaxLength(vector<int>& nums)
{
int n = nums.size();
int res = 0;
unordered_map<int,int> first_ID; //第一次出现的位置
first_ID[0] = -1; //dp初始化
int cnt0 = 0, cnt1 = 0;
for (int i = 0; i < n; i ++)
{
cnt0 += (nums[i] == 0);
cnt1 += (nums[i] == 1);
int d = cnt0 – cnt1; //平衡因子
if (first_ID.count(d))
res = max(res, i – first_ID[d]);
else
first_ID[d] = i;
}
return res;
}
};
6. 搜索二维矩阵
74. 搜索二维矩阵https://leetcode.cn/problems/search-a-2d-matrix/
给你一个满足下述两条属性的 m x n 整数矩阵：
- 每行中的整数从左到右按非严格递增顺序排列。
- 每行的第一个整数大于前一行的最后一个整数。
给你一个整数 target ，如果 target 在矩阵中，返回 true ；否则，返回 false 。
写法一：二分查找
class Solution {
public:
bool searchMatrix(vector<vector<int>>& matrix, int target) {
int left=0,right=matrix[0].size()-1,floor=0;
while(left<right&&floor<matrix.size())
{
while(floor<matrix.size()&&target>matrix[floor][right])
floor++;
if(floor==matrix.size())
return false;
int mid=left+(right-left+1)/2; //二分查找
if(matrix[floor][mid]<=target)
left=mid;
else
right=mid-1;
}
while(floor<matrix.size()&&target>matrix[floor][right])
floor++;
if(floor==matrix.size())
return false;
if(matrix[floor][left]==target)
return true;
else
return false;
}
};
写法二：排除法
class Solution {
public:
bool searchMatrix(vector<vector<int>>& matrix, int target) {
int m = matrix.size(), n = matrix[0].size();
int i = 0, j = n – 1;
while (i < m && j >= 0) { // 还有剩余元素
if (matrix[i][j] == target) {
return true; // 找到 target
}
if (matrix[i][j] < target) {
i++; // 这一行剩余元素全部小于 target，排除
} else {
j–; // 这一列剩余元素全部大于 target，排除
}
}
return false;
}
};
7. 矩阵区域和⭐
1314. 矩阵区域和https://leetcode.cn/problems/matrix-block-sum/
给你一个 m x n 的矩阵 mat 和一个整数 k ，请你返回一个矩阵 answer ，其中每个 answer[i][j] 是所有满足下述条件的元素 mat[r][c] 的和：
- i – k <= r <= i + k,
- j – k <= c <= j + k 且
- (r, c) 在矩阵内。
class Solution {
public:
vector<vector<int>> matrixBlockSum(vector<vector<int>>& mat, int K) {
int m = mat.size(), n = mat[0].size();
vector<vector<int>> preadd(m+1,vector<int>(n+1,0));
for(int i=1;i<=m;i++)
{
for(int j=1;j<=n;j++)
{
preadd[i][j]=preadd[i-1][j]+preadd[i][j-1]-preadd[i-1][j-1]+mat[i-1][j-1];
}
}
vector<vector<int>> ans(m, vector<int>(n, 0));
for(int i=0;i<m;++i)
{
for(int j=0;j<n;j++)
{
// 计算左上角坐标 (row1, col1) 和右下角坐标 (row2, col2)
int row1 = max(i – K, 0) + 1, col1 = max(j – K, 0) + 1;
int row2 = min(i + K, m – 1) + 1, col2 = min(j + K, n – 1) + 1;
ans[i][j]=preadd[row2][col2]+preadd[row1-1][col1-1]-preadd[row2][col1-1]-preadd[row1-1][col2];
}
}
return ans;
}
};
注意：这里的二维下标逻辑很关键
