给你一个整数数组 `nums` ，判断是否存在三元组 `[nums[i], nums[j], nums[k]]` 满足 `i != j`、`i != k` 且 `j != k` ，同时还满足 `nums[i] + nums[j] + nums[k] == 0` 。请
你返回所有和为 `0` 且不重复的三元组。
**注意：**答案中不可以包含重复的三元组。
- 排序,先一层的for循环,然后第二层,使用两数之和的方式实现
给你一个整数数组 `nums`，返回 _数组 `answer` ，其中 `answer[i]` 等于 `nums` 中除 `nums[i]` 之外其余各元素的乘积_ 。
题目数据 **保证** 数组 `nums`之中任意元素的全部前缀元素和后缀的乘积都在 **32 位** 整数范围内。
请**不要使用除法，**且在 `O(_n_)` 时间复杂度内完成此题。
给你一个整数数组 `nums` 和一个整数 `k` ，请你统计并返回 _该数组中和为 `k` 的连续子数组的个数_ 。
class Solution {
public:
int subarraySum(vector<int>& nums, int k) {
unordered_map<int, int> mp;
mp[0] = 1;
int count = 0, pre = 0;
for (auto& x:nums) {
pre += x;
if (mp.find(pre - k) != mp.end()) {
count += mp[pre - k];
}
mp[pre]++;
}
return count;
}
};
给定一个二进制数组 `nums` , 找到含有相同数量的 `0` 和 `1` 的最长连续子数组，并返回该子数组的长度。
给你一个整数数组 `nums` 和一个整数 `k` ，编写一个函数来判断该数组是否含有同时满足下述条件的连续子数组：
- 子数组大小 **至少为 2** ，且
- 子数组元素总和为 `k` 的倍数。
如果存在，返回 `true` ；否则，返回 `false` 。
如果存在一个整数 `n` ，令整数 `x` 符合 `x = n * k` ，则称 `x` 是 `k` 的一个倍数。`0` 始终视为 `k` 的一个倍数。
- 也是前缀加hash的特殊模式,但是巧妙的地方在于当prefix[i]-prefix[j]是k的倍数的时候,prefix[i]和prefix[j]除以 k的余数相同
给定一个数组(10^5),求平均值为k的最长子数组的长度
- 本质还是前缀+hash,但是需要变通一下,首先将平均值转换为长度*和的形式,和可以用前缀求
// (i-j+1)*k=arr[i]+...+arr[j]
//=> i*k-j*k+k=prefix[i]-prefix[j]+arr[i]
//=> pre[j]-j*k+k=pre[i]-i*k+arr[i]
//前面的作为hash存储,后面的作为key遍历寻找值
vector<int> arr(size,0);
unordered_map<long long , long long> hashmap;
long long prefix=0,result=-1;
for (int i = 0; i < size; i++) {
if (hashmap.find(prefix-i*k+arr[i])!=hashmap.end()) {
auto temp=hashmap[prefix-i*k+arr[i]];
result=max(result,(long long)i-temp+1);
}
long long val=prefix-i*k+k;
if (hashmap.find(val)==hashmap.end()) {
hashmap[val]=i;
}
prefix+=arr[i];
}
给定一个二维矩阵 `matrix`，以下类型的多个请求：
- 计算其子矩形范围内元素的总和，该子矩阵的 **左上角** 为 `(row1, col1)` ，**右下角** 为 `(row2, col2)` 。
实现 `NumMatrix` 类：
- `NumMatrix(int[][] matrix)` 给定整数矩阵 `matrix` 进行初始化
- `int sumRegion(int row1, int col1, int row2, int col2)` 返回 **左上角** `(row1, col1)` 、**右下角** `(row2, col2)` 所描述的子矩阵的元素 **总和** 。
- 特殊前缀和,这个前缀是矩阵的前缀即(0,0)->(n,n)前缀和
给你两个下标从 **0** 开始的数组 `nums` 和 `cost` ，分别包含 `n` 个 **正** 整数。
你可以执行下面操作 **任意** 次：
- 将 `nums` 中 **任意** 元素增加或者减小 `1` 。
对第 `i` 个元素执行一次操作的开销是 `cost[i]` 。
请你返回使 `nums` 中所有元素 **相等** 的 **最少** 总开销。
- 很有意思的前缀和,最后成为的数字一定是其中的数组某个数字,只需要计算变成每个数字开销分别是多少就可以了,这个使用前缀前面一个很容易推出下一个
for (int i = 0; i < nums.size(); i++) {
arr[i].first=nums[i];
arr[i].second=cost[i];
}
sort(arr.begin(),arr.end());
vector<long long> pre(nums.size(),0),end(nums.size(),0);
long long now=arr[0].second;
for (int i = 1; i < nums.size(); i++) {
pre[i]=pre[i-1]+(arr[i].first-arr[i-1].first)*now;
now+=arr[i].second;
}
now=arr[nums.size()-1].second;
for (int i = nums.size()-2; i >=0; i--) {
end[i]=end[i+1]+(arr[i+1].first-arr[i].first)*now;
now+=arr[i].second;
}
for (int i = 0; i < nums.size(); i++) {
result=min(result,pre[i]+end[i]);
}