力扣题的前缀和功能，你能详细解释一下吗？
摘要：前缀和力扣题（leetcode） 238. 除了自身以外数组的乘积 难度：中等 相关标签：数组、前缀和 题目： 给你一个整数数组 nums，返回 数组 answer ，其中 answer[i] 等于 nums 中除了 nums[i] 之外其
前缀和力扣题（leetcode）
238. 除了自身以外数组的乘积
难度：中等
相关标签：数组、前缀和
题目：
给你一个整数数组 nums，返回 数组 answer ，其中 answer[i] 等于 nums 中除了 nums[i] 之外其余各元素的乘积 。
题目数据 保证 数组 nums之中任意元素的全部前缀元素和后缀的乘积都在 32 位 整数范围内。
请 不要使用除法，且在 O(n) 时间复杂度内完成此题。
示例 1:
输入: nums = [1,2,3,4]
输出: [24,12,8,6]
示例 2:
示例 2:
输入: nums = [-1,1,0,-3,3]
输出: [0,0,9,0,0]
提示：
\(2 <= nums.length <= 10^5\)
\(-30 <= nums[i] <= 30\)
\(输入 保证 数组 answer[i] 在 32 位 整数范围内\)
进阶：你可以在 O(1) 的额外空间复杂度内完成这个题目吗？（ 出于对空间复杂度分析的目的，输出数组 不被视为 额外空间。）
代码：
class Solution
{
public:
vector<int> productExceptSelf(vector<int>& nums)
{
int n = nums.size();
vector<int> res(n, 1); // 结果数组，初始化为1（乘法的单位元）
// 第一步：计算前缀积（复用res数组存前缀积）
// pre[i] = nums[0] * nums[1] * ... * nums[i-1]
int pre = 1;
for (int i = 0; i < n; i++)
{
res[i] = pre; // 先存前缀积（此时res[i]是左侧所有元素的积）
pre *= nums[i]; // 更新前缀积
}
// 第二步：计算后缀积，并和前缀积相乘得到最终结果
// suf[i] = nums[i+1] * nums[i+2] * ... * nums[n-1]
int suf = 1;
for (int i = n - 1; i >= 0; i--)
{
res[i] *= suf; // 前缀积 × 后缀积 = 最终结果
suf *= nums[i]; // 更新后缀积
}
return res;
}
};
相似题目
接雨水困难
乘积最大子数组中等
粉刷房子 II困难
删除元素后和的最小差值困难
构造乘积矩阵中等
魔法序列的数组乘积之和困难
253. 会议室 II
难度：中等
相关标签：贪心、数组、双指针、前缀和、排序堆（优先队列）
题目：
给你一个会议时间安排的数组 \(intervals\)，每个会议时间都会包括开始和结束的时间 \(intervals[i] = [starti, endi]\)，返回 所需会议室的最小数量 。
示例 1:
输入：intervals = [[0,30],[5,10],[15,20]]
输出：2
示例 2:
输入：intervals = [[7,10],[2,4]]
输出：1
提示：
\(1 <= intervals.length <= 10^4\)
\(0 <= start_i < end_i <= 10^6\)
代码：
class Solution
{
public:
int minMeetingRooms(vector<vector<int>>& intervals)
{
vector<int> starts, ends;
for (auto& interval : intervals)
{
starts.push_back(interval[0]);
ends.push_back(interval[1]);
}
sort(starts.begin(), starts.end());
sort(ends.begin(), ends.end());
int res = 0, current = 0, i = 0, j = 0;
while (i < intervals.size())
{
if (starts[i] < ends[j])
{
current++; // 会议开始，占用+1（前缀和+1）
res = max(res, current);
i++;
}
else
{
current--; // 会议结束，占用-1（前缀和-1）
j++;
}
}
return res;
}
};
相似题目
合并区间中等
会议室简单
用最少数量的箭引爆气球中等
拼车中等
花期内花的数目困难
会议室 III困难
雇佣 K 位工人的总代价中等
与车相交的点简单
560. 和为 K 的子数组
难度：中等
相关标签：数组、哈希表、前缀和
题目：
给你一个整数数组 nums 和一个整数 k ，请你统计并返回 该数组中和为 k 的子数组的个数 。
子数组是数组中元素的连续非空序列。
示例 1:
输入：nums = [1,1,1], k = 2
输出：2
示例 2:
输入：nums = [1,2,3], k = 3
输出：2
提示：
\(1 <= nums.length <= 2*10^4\)
\(-1000 <= nums[i] <= 1000\)
\(-10^7 <= k <= 10^7\)
代码：
class Solution
{
public:
int subarraySum(vector<int>& nums, int k)
{
int n = nums.size();
if(n == 0) return 0;
// 第一步：预处理前缀和
vector<int> s(n, 0);
s[0] = nums[0];
for(int i = 1; i < n; i++)
{
s[i] = s[i-1] + nums[i];
}
// 哈希表记录前缀和s[0...r-1]出现的次数
unordered_map<int, int> sCnt;
sCnt[0] = 1;// 初始化：s[0]=0 出现1次（对应你原代码l=1的边界）
int cnt = 0;
for(int r = 0; r < n; r++)
{
int target = s[r] - k;// 核心公式：s[r] - s[l-1] = k → s[l-1] = s[r] - k
if(sCnt.find(target) != sCnt.end()) cnt+= sCnt[target];
sCnt[s[r]]++;
}
return cnt;
}
};
两数之和简单
连续的子数组和中等
乘积小于 K 的子数组中等
寻找数组的中心下标简单
和可被 K 整除的子数组中等
将 x 减到 0 的最小操作数中等
半径为 k 的子数组平均值中等
数组的最大总分中等