数组问题
1.数组问题是在数组内解决的问题, 用到的方法一切皆有可能, 常用的一些方法包括 dp, 双指针, 滑动窗口, 回溯, 模拟, 哈希, 二分查找等
2.数组有一类问题, 是定义在数组这个基础结构之上的一些数据结构去解决问题, 包括前缀和数组和差分数组
(i). 前缀和数组
(ii). 差分数组
前缀和数组
1.前缀和是记录 prefixSum 是记录第 i 个元素之前的所有元素的和, 比如 prefixSum[1] 记录的是 nums[0], 我们将这种数组简写成 preSum; 特殊情况 preSum[0] = 0 不影响计算的结果
preSum[0] = 0
preSum[1] = nums[0]
preSum[2] = nums[0] + nums[1]
...
preSum[i] = sum(nums[0]..nums[i-1])
2.前缀和数组之间的递推关系, 对应的物理意义是: 当前这个数的前缀和它前面的前缀和, 差距正好是当前这个元素
preSum[i] = preSum[i-1] + nums[i-1]
3.迭代构建前缀和数组, 对于一个长度为 n 的数组, 构建长度为 n+1 的前缀和数组如下
int n = nums.size();
vector<int> preSum(n+1, 0);
for (int i = 1; i < n + 1; ++i) {
preSum[i] = preSum[i-1] + nums[i-1];
}
4.前缀和数组的提出原因是希望高效地计算一个数组中某个连续区间 nums[i..j] 之间的区间求和的问题, 当我们涉及到求某个数组之间的连续值之间和相关的计算的时候, 我们先联想到用前缀和来简化时间:
(i). 如果我们在不采用前缀和数组的情况下, 我们会先扫描 nums 到 i, 然后再顺序扫描 i..j 个元素求和, 时间复杂度是 O(n)
(ii). 顺序扫描的过程中, 每次查询的索引 [i_1, j_1], [i_2, j_2], [i_3, j_3] 我们都要执行上述的扫描过程; 这里的优化空间是, 所有的查询索引对都是从0 开始的, 两个索引 i 和 j 之间存在一定关系, sumRange(0..j) 和sumRange(0..i) 之间的差就是我们要的 sumRange (i..j), 其中 sumRange(0..i)
5.举例:
如果有 nums 为 [-2,0,3,-5,2,-1], 我们首先构造它的前缀和数组为 preSum[0,-2,-2,1,-4,-2,-3]
sumRange[2,5], 计算preSum[6]-preSum[2] = -3 - (-2) = -1
sumRange[0,5], 计算preSum[6]-preSum[0] = -3 - 0 = -3
sumRange[0,2], 计算preSum[3]-preSum[0] = 1 - 0 = 1
…
sumRange(i,j) = preSum(j+1,i)
6.定义前缀和数组还有另一种定义的方法: 定义包含位置 i 元素在内的 前 i 个元素之和: 这时候的递推关系为
preSum[i] = nums[0]
for (int i = 1; i < len.size(); ++i) {
preSum[i] = preSum[i-1] + nums[i];
}
7.从实际解决问题的过程来看, 有时候可以同时遍历和构建前缀和数组;
303.前缀和数组
给定一个整数数组 nums，处理以下类型的多个查询: 计算索引 left 和 right （包含 left 和 right）之间的 nums 元素的 和 ，其中 left <= right 实现 NumArray 类：NumArray(int[] nums) 使用数组 nums 初始化对象
int sumRange(int i, int j)
返回数组 nums 中索引 left 和 right 之间的元素的 总和 ，包含 left 和 right 两点（也就是 nums[left] + nums[left + 1] + … + nums[right])示例 1：输入：[“NumArray”, “sumRange”, “sumRange”, “sumRange”] [[[-2, 0, 3, -5, 2, -1]], [0, 2], [2, 5], [0, 5]] 输出：[null, 1, -1, -3]
解释：
NumArray numArray = new NumArray([-2, 0, 3, -5, 2, -1]);
numArray.sumRange(0, 2); // return 1 ((-2) + 0 + 3)
numArray.sumRange(2, 5); // return -1 (3 + (-5) + 2 + (-1))
numArray.sumRange(0, 5); // return -3 ((-2) + 0 + 3 + (-5) + 2 + (-1))
分析:
1.前缀和数组问题, 构造前缀和数组
2.sumRange(i..j) = preSum[j+1] - preSum[i]
class NumArray {
private:
vector<int> preSum;
public:
NumArray(vector<int>& nums) {
int len = nums.size();
preSum = vector<int>(len + 1, 0);
for (int i = 1; i < len + 1; ++i) {
preSum[i] = preSum[i-1] + nums[i-1];
}
}
int sumRange(int left, int right) {
return preSum[right + 1] - preSum[left];
}
};
304.二维区域和检索-矩阵不可变
给定一个二维矩阵 matrix，以下类型的多个请求：
计算其子矩形范围内元素的总和，该子矩阵的 左上角 为 (row1, col1) ，右下角 为 (row2, col2) 。
实现 NumMatrix 类：
NumMatrix(int[][] matrix) 给定整数矩阵 matrix 进行初始化
int sumRegion(int row1, int col1, int row2, int col2) 返回 左上角 (row1, col1) 、右下角 (row2, col2) 所描述的子矩阵的元素 总和 。示例 1：输入: [“NumMatrix”,”sumRegion”,”sumRegion”,”sumRegion”]
[[[[3,0,1,4,2],[5,6,3,2,1],[1,2,0,1,5],[4,1,0,1,7],[1,0,3,0,5]]],[2,1,4,3],[1,1,2,2],[1,2,2,4]]
输出: [null, 8, 11, 12]
解释:
NumMatrix numMatrix = new NumMatrix([[3,0,1,4,2],[5,6,3,2,1],[1,2,0,1,5],[4,1,0,1,7],[1,0,3,0,5]]);
numMatrix.sumRegion(2, 1, 4, 3); // return 8 (红色矩形框的元素总和)
numMatrix.sumRegion(1, 1, 2, 2); // return 11 (绿色矩形框的元素总和)
numMatrix.sumRegion(1, 2, 2, 4); // return 12 (蓝色矩形框的元素总和)
分析:
1.前缀和数组的二维版本, 矩阵的特点是从[0,0]开始计算, 所以我们可以构建二维前缀和数组preSum[i,j] = 以[i-1, j-1]作为右下角节点的矩阵元素和, 也就是计算矩阵[0,0,i-1,j-1]之和,
preSum[1,1] = matrix([0,0])
preSum[1,2] = matrix([0,0], [0,1])
preSum[2,2] = matrix([0,0], [0,1], [1,0], [1,1])
2.计算前缀和的时需要想清楚前缀和的迭代关系, 这个迭代关系是由摩根率直接算的, 中间区域多算了一次需要被剔除掉
preSum[i][j] = presum[i-1][j] + preSum[i][j-1] + matrix[i-1][j-1] - preSum[i-1][j-1]
3.任意子矩阵元素之和可以转化为几个[0, 0]开头的矩阵经过摩根律计算得到的元素之和, 中间区域被多减去的一次需要再加回来
sumRegion(0,0,2,2) = preSum[3,3] - preSum[2,3] + preSum[3,2] - preSum[2,2]
sumRegion(0,0,2,1) = preSum[3,2] - preSum[2,2] + preSum[3,1] - preSum[2,1]
4.sumRegion(x1,y1,x2,y2) = preSum[x2+1][y2+1] - preSum[x1][y2+1] - preSum[x2+1][y1] + preSum[x1][y1]
class NumMatrix {
private:
vector<vector<int>> preSum;
public:
NumMatrix(vector<vector<int>>& matrix) {
int m = matrix.size();
if (m > 0) {
int n = matrix[0].size();
preSum.resize(m+1, vector<int>(n+1));
for (int i = 1; i <= m; ++i) {
for (int j = 1; j <= n; ++j) {
preSum[i][j] = preSum[i-1][j] + preSum[i][j-1] + matrix[i-1][j-1] - preSum[i-1][j-1];
}
}
}
}
int sumRegion(int row1, int col1, int row2, int col2) {
return preSum[row2+1][col2+1]-preSum[row1][col2+1]-preSum[row2+1][col1]+preSum[row1][col1];
}
};
/**
* Your NumMatrix object will be instantiated and called as such:
* NumMatrix* obj = new NumMatrix(matrix);
* int param_1 = obj->sumRegion(row1,col1,row2,col2);
*/
560.和为 K 的子数组
给你一个整数数组 nums 和一个整数 k ，请你统计并返回 该数组中和为 k 的子数组的个数 。子数组是数组中元素的连续非空序列。
示例 1：输入：nums = [1,1,1], k = 2 输出：2
示例 2：输入：nums = [1,2,3], k = 3 输出：2
分析:
1.题目中要求的是计算数组中连续子数组的求和 == k的情况, 我们看到连续子数组求和马上联想到前缀和数组看看能不能加快计算, 因为要求的是连续子数组和 == k, 那么其实转化到前缀和数组上就是问两个前缀和的差 == k的情况
2.我们用带包含的定义 preSum[i] 是包含第 i 个元素的前缀和, 也就是
preSum[i] = preSum[i - 1] + num[i]
3.对于任意的两个下标 i 和 j（i < j），如果 prefixSum[j] - prefixSum[i] = k，即从第 i 个位置到第 j 个位置的元素之和等于 k, 那么说明从第 i+1 个位置到第 j 个位置的连续子数组的和为 k
先遍历 1 次数组, 得到前缀和数组, 开一个哈希表来存储每种前缀和出现的次数. 在遍历的过程中, 我们检查是否存在 prefixSum[j] - k的前缀和, 如果存在，说明从某个位置到当前位置的连续子数组的和为 k, 我们将对应的次数累加到结果中
再遍历一次数组，累加出和为 k 的连续子数组的个数，最终时间复杂度为 O(n)
class Solution {
public:
int subarraySum(vector<int>& nums, int k) {
int n = nums.size();
if (n == 0) {
return 0;
}
int ans = 0;
// 构建包含i的前缀数组
vector<long> preSum(n, 0);
preSum[0] = nums[0];
for (int i = 1; i < n; ++i) {
preSum[i] = preSum[i-1] + nums[i];
}
// preSum2Cnt 记录每一种前缀和出现的次数
unordered_map<long, int> preSum2Cnt;
preSum2Cnt[0] = 1;
for (int i = 0; i < n; ++i) {
// 如果 preSum[i] - k 这种前缀和是存在的, 那么答案累加这种前缀和的次数, 同时累加这种前缀和出现的次数
if (preSum2Cnt.find(preSum[i] - k) != preSum2Cnt.end()) {
ans += preSum2Cnt[preSum[i] - k];
}
// 累加前缀和出现的次数
preSum2Cnt[preSum[i]] += 1;
}
return ans;
}
};
对每个位置 i, 计算前缀和只需用 1 次, 因此前缀和计算和累加前缀和是可以同时进行, 不需要开数组, 只维护当前那个前缀和出现的次数
class Solution {
public:
int subarraySum(vector<int>& nums, int k) {
int n = nums.size();
int ans = 0;
if (n == 0) {
return 0;
}
long preSum = 0;
unordered_map<long, int> preSum2Cnt;
preSum2Cnt[0] = 1;
for (int i = 0; i < n; ++i) {
preSum += nums[i];
if (preSum2Cnt.find(preSum - k) != preSum2Cnt.end()) {
ans += preSum2Cnt[preSum - k];
}
preSum2Cnt[preSum] += 1;
}
return ans;
}
};
325.和等于 k 的最长子数组长度
给定一个数组 nums 和一个目标值 k，找到和等于 k 的最长连续子数组长度。如果不存在任意一个符合要求的子数组，则返回 0。
示例 1: 输入: nums = [1,-1,5,-2,3], k = 3 输出: 4 解释: 子数组 [1, -1, 5, -2] 和等于 3，且长度最长。
示例 2: 输入: nums = [-2,-1,2,1], k = 1 输出: 2 解释: 子数组 [-1, 2] 和等于 1，且长度最长。
分析:
1.看到连续子数组, 直接用前缀和先算一遍, 我们还是用带包含 i 位置的前缀和的定义,
class Solution {
public:
int maxSubArrayLen(vector<int>& nums, int k) {
int n = nums.size();
if (n == 0) {
return 0;
}
int ans = 0;
vector<long> preSum(n, 0);
preSum[0] = nums[0];
for (int i = 1; i < n; ++i) {
preSum[i] = preSum[i-1] + nums[i];
}
unordered_map<long, int> preSum2FirstIdx;
preSum2FirstIdx[0] = 0;
for (int i = 0; i < n; ++i) {
// 如果是前缀和第一次出现, 记录第一个位置
if (preSum2FirstIdx.find(preSum[i]) == preSum2FirstIdx.end()) {
preSum2FirstIdx[preSum[i]] = i + 1;
}
if (preSum2FirstIdx.find(preSum[i] - k) != preSum2FirstIdx.end()) {
ans = max(ans, i + 1 - preSum2FirstIdx[preSum[i] - k]);
}
}
return ans;
}
};
一次遍历, 只维护当前的解法
class Solution {
public:
int maxSubArrayLen(vector<int>& nums, int k) {
int n = nums.size();
if (n == 0) {
return 0;
}
int ans = 0;
long preSum = 0;
unordered_map<long, int> preSum2FirstIdx;
preSum2FirstIdx[0] = 0;
for (int i = 0; i < n; ++i) {
preSum += nums[i];
// 仅当第一次出现的时候才记录位置: 记录第一个位置
if (preSum2FirstIdx.find(preSum) == preSum2FirstIdx.end()) {
preSum2FirstIdx[preSum] = i + 1;
}
if (preSum2FirstIdx.find(preSum - k) != preSum2FirstIdx.end()) {
ans = max(ans, i + 1 - preSum2FirstIdx[preSum - k]);
}
}
return ans;
}
};
128.最长连续序列
给定一个未排序的整数数组 nums ，找出数字连续的最长序列（不要求序列元素在原数组中连续）的长度。请你设计并实现时间复杂度为 O(n) 的算法解决此问题。
示例 1：输入：nums = [100,4,200,1,3,2] 输出：4 解释：最长数字连续序列是 [1, 2, 3, 4]。它的长度为 4。
示例 2：输入：nums = [0,3,7,2,5,8,4,6,0,1] 输出：9
分析:
1.时间复杂度要求是 O(n), 排序之类的都不能用
2.这里关键是分析连续序列有什么特殊性? 对于连续的序列, 它的很多子序列对我们计算最长序列长度没有影响, 比如对 1,2,3,4 这个序列, 对于它的子序列, 例如 2,3,4 或者 3,4, 不会增加最大长度序列的可能性; 如果能想到研究对象缩短到研究, 当前的数字是否是某个最长序列的 [判断可能是一个最长连续序列的起点], 那么复杂度就不会增加; 也就是说, 我们对任意一个数字, 判断当前的数字是 [可能是一个最长连续序列的起点] 的时候, 才会进入内层统计长度, 因此时间复杂度是 O(n)
3.用一个 set 去保存元素, 然后遍历 set , 每个元素首先检查是否是第一个元素, 如果不是那么就不进入扫描最长连续长度
class Solution {
public:
int longestConsecutive(vector<int>& nums) {
if (nums.empty()) {
return 0;
}
unordered_set<int> s(nums.begin(), nums.end());
int ans = 1;
for (auto x: s) {
// 判断可能是一个最长连续序列的起点
if (!s.count(x - 1)) {
int len = 1;
int cur = x;
// 进入里面开始逐个判断以它为起点的最长长度
while (s.count(cur + 1)) {
++len;
++cur;
}
ans = max(len, ans);
}
}
return ans;
}
};
845.数组中的最长山脉
把符合下列属性的数组 arr 称为 山脉数组 ：
arr.length >= 3 存在下标 i（0 < i < arr.length - 1），满足
arr[0] < arr[1] < … < arr[i-1] < arr[i]
arr[i] > arr[i + 1] > … > arr[arr.length - 1]
给出一个整数数组 arr，返回最长山脉子数组的长度。如果不存在山脉子数组，返回 0 。示例 1：输入：arr = [2,1,4,7,3,2,5] 输出：5 解释：最长的山脉子数组是 [1,4,7,3,2]，长度为 5。
示例 2：输入：arr = [2,2,2] 输出：0 解释：不存在山脉子数组。
分析:
1.找到每一个[山顶], 然后计算左边和右边的最大长度, 遍历山顶找最大的
2.left[i]表示nums[i]左边可以扩展的最大长度 left[i]和left[i-1]的关系是什么?
3.状态转移方程
if nums[i-1] < nums[i]: left[i] = left[i-1] + 1
if nums[i-1] >= nums[i]: left[i] = 0
特殊情况下: left[0] = 0
右侧同理, right[i] = right[i+1] + 1 when nums[i+1] > nums[i]
4.判断是山顶的条件 left > 0 && right > 0, 这时候山脉长度 = left[i] + right[i] + 1
class Solution {
public:
int longestMountain(vector<int>& arr) {
if (arr.empty())
return 0;
int n = arr.size();
vector<int> l(n, 0);
vector<int> r(n, 0);
for (int i = 1; i < n; ++i) {
if (arr[i-1] < arr[i]) {
l[i] = max(0, l[i-1] + 1);
}
}
for (int i = n-2; i >= 0; --i) {
if (arr[i+1] < arr[i]) {
r[i] = max(0, r[i+1] + 1);
}
}
int ans = 0;
for (int i = 0; i < n; ++i) {
if (l[i] > 0 && r[i] > 0) {
ans = max(ans, l[i] + r[i] + 1);
}
}
return ans;
}
};
238.除自身以外数组的乘积
给你一个整数数组 nums，返回 数组 answer ，其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积 。 题目数据 保证 数组 nums之中任意元素的全部前缀元素和后缀的乘积都在 32 位 整数范围内。请不要使用除法，且在 O(n) 时间复杂度内完成此题。
示例 1: 输入: nums = [1,2,3,4] 输出: [24,12,8,6]
示例 2: 输入: nums = [-1,1,0,-3,3] 输出: [0,0,9,0,0]
分析:
1.我们不妨想一下出题人想考我们什么, 想要 [除自身以外数组的乘积] 可以直接全部乘起来然后除以 [自身], 但是这种直觉的想法有个问题是无法处理自身为 0 的问题, 所以提示了不要使用除法
2.思路上很类似于接雨水的思路, 我们首先构造一个左侧乘积数组, 对于某个元素 i 来说, lProduct[i] 是它严格左侧所有的乘积; 同理右侧侧乘积数组 rProduct[i] 是它严格右侧所有的乘积, 然后遍历取 lProduct[i] * rProduct[i]; 对于边界条件设定 lProduct[0] = 1 = rProduct[len - 1]
class Solution {
public:
vector<int> productExceptSelf(vector<int>& nums) {
int len = nums.size();
vector<int> lProduct(len, 1); // 存储左侧所有元素乘积
vector<int> rProduct(len, 1); // 存储右侧所有元素乘积
vector<int> ans(len, 0);
for (int i = 1; i < len; ++i) {
lProduct[i] = lProduct[i-1] * nums[i-1];
}
for (int i = len - 2; i >= 0; --i) {
rProduct[i] = rProduct[i+1] * nums[i+1];
}
for (int i = 0; i < len; ++i) {
ans[i] = lProduct[i] * rProduct[i];
}
return ans;
}
};
1046.最后一块石头的重量
有一堆石头，每块石头的重量都是正整数。
每一回合，从中选出两块 最重的 石头，然后将它们一起粉碎。假设石头的重量分别为 x 和 y，且 x <= y。那么粉碎的可能结果如下：
如果 x == y，那么两块石头都会被完全粉碎；如果 x != y，那么重量为 x 的石头将会完全粉碎，而重量为 y 的石头新重量为 y-x。
最后，最多只会剩下一块石头。返回此石头的重量。如果没有石头剩下，就返回 0。示例：输入：[2,7,4,1,8,1] 输出：1
解释：
先选出 7 和 8，得到 1，所以数组转换为 [2,4,1,1,1]，
再选出 2 和 4，得到 2，所以数组转换为 [2,1,1,1]，
接着是 2 和 1，得到 1，所以数组转换为 [1,1,1]，
最后选出 1 和 1，得到 0，最终数组转换为 [1]，这就是最后剩下那块石头的重量。
分析:
1.直接找最大的两块石头去模拟, 采用大顶堆去保存所有数字, 然后每次取出前两个进行判断是否要加入
class Solution {
public:
int lastStoneWeight(vector<int>& stones) {
if (stones.empty()) {
return 0;
}
priority_queue<int> q;
for (int n: stones) {
q.push(n);
}
while (q.size() > 1) {
int first = q.top();
q.pop();
int second = q.top();
q.pop();
if (first != second) {
q.push(first - second);
}
}
return q.empty() ? 0 : q.top();
}
};
152.乘积最大子数组
给你一个整数数组 nums ，请你找出数组中乘积最大的非空连续子数组（该子数组中至少包含一个数字），并返回该子数组所对应的乘积。测试用例的答案是一个 32-位 整数。子数组 是数组的连续子序列。
示例 1: 输入: nums = [2,3,-2,4] 输出: 6 解释: 子数组 [2,3] 有最大乘积 6。
示例 2: 输入: nums = [-2,0,-1] 输出: 0 解释: 结果不能为 2, 因为 [-2,-1] 不是子数组。
class Solution {
public:
int maxProduct(vector<int>& nums) {
}
};
628.三个数的最大乘积
给你一个整型数组 nums ，在数组中找出由三个数组成的最大乘积，并输出这个乘积。
示例 1：输入：nums = [1,2,3] 输出：6
示例 2：输入：nums = [1,2,3,4] 输出：24
示例 3：输入：nums = [-1,-2,-3] 输出：-6
class Solution {
public:
int maximumProduct(vector<int>& nums) {
}
};
713. 乘积小于 K 的子数组
给你一个整数数组 nums 和一个整数 k ，请你返回子数组内所有元素的乘积严格小于 k 的连续子数组的数目。
示例 1：输入：nums = [10,5,2,6], k = 100 输出：8
解释：8 个乘积小于 100 的子数组分别为：[10]、[5]、[2],、[6]、[10,5]、[5,2]、[2,6]、[5,2,6]。
需要注意的是 [10,5,2] 并不是乘积小于 100 的子数组。示例 2：输入：nums = [1,2,3], k = 0 输出：0
class Solution {
public:
int numSubarrayProductLessThanK(vector<int>& nums, int k) {
}
};
转载请注明来源 goldandrabbit.github.io