前缀和力扣题（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] - kif(sCnt.find(target) != sCnt.end()) cnt+= sCnt[target];sCnt[s[r]]++;}return cnt;}
};
两数之和简单
连续的子数组和中等
乘积小于 K 的子数组中等
寻找数组的中心下标简单
和可被 K 整除的子数组中等
将 x 减到 0 的最小操作数中等
半径为 k 的子数组平均值中等
数组的最大总分中等