今日学习记录
1. 全 0 子数组的数目leetcode.2348
关键词：双指针 数学
问题分析：
- 给你一个整数数组 nums ，返回全部为
0的 子数组 数目。
核心思路
- 先看一个范围内连续的 0 数组个数,能组成的不同数组数为,很好推都数学公式
- 用双指针求 0 的范围个数和统计范围内的 0 个数
- 定义 fast 和 low,遍历数组,当遍历到 0,再让 fast 往后遍历有多少个 0,统计 0 的个数累加
- 每次合并两指针,时间复杂度为 1,无额外空间开销
- 还可以滑窗,但没我上面直接计算快,就不用了;
- 还有增量法,都是基于双指针的,也没我上面的快
**最终代码：
long long zeroFilledSubarray(vector<int>& nums) {
long long ans = 0;
int n = 0;
for(int fast = 0,low = 0;fast<nums.size();fast++){
if(nums[fast]==0){
low = fast;
while(fast+1<nums.size()&&!nums[fast+1]) fast++;
n = fast-low+1;
ans += (long long)n*(n+1)/2;
}
}
return ans;
}学到的点：
- 简单到爆
- 越小越合法的滑动窗口
- 增量法
2. 等差数列划分leetcode.413
关键词：双指针
问题分析：
- 给你一个整数数组 nums,返回数组 nums 中所有为等差数组的子数组个数.
- 这个数列至少有三个元素
核心思路
- 还是双指针,但是怎么换差分我就不熟了呢,不就是要找到第一个符合条件的点,再往后面找符合该条件的连续区间,然后统计区间长度,在做计算
- 就是 i 站桩,j 往后找,while 增加 j,取 j 中间的数量,不用额外变量来计数,不准确,直接 j-i+1,再在后面减 3 进行计算,方便不易错,最后合并 i 和 j,i 都不用 i++了
最终代码：
int numberOfArithmeticSlices(vector<int>& nums) {
int n = nums.size();
if(n<3) return 0;
int ans = 0;
int len = 0,an = 0;
int count = 0;
for(int i = 0;i<n-2;){
int j = i,d = nums[i+1] - nums[i];
while(j+1<n&&nums[j+1]-nums[j]==d) j++;
len = j-i+1,an = len - 3+1;
count = (1+an)*an/2;
ans += count;
i = j;
}
return ans;
}学到的点：
- 双指针
今日收获
-
新技巧：
- 双指针
-
待加强：
- 差分数组,前缀和
-
明日计划：
- [ ]
- [ ]