C++实现一个序列的所有连续子段的乘积
时间: 2024-02-11 14:08:52 浏览: 59
可以使用双指针法来实现,具体步骤如下:
1. 定义两个指针left和right,分别指向序列的开头和结尾。
2. 定义一个变量product,用于存储连续子段的乘积,初始化为1。
3. 定义一个向量result,用于存储所有连续子段的乘积。
4. 循环遍历序列,每次将right向右移动一位,同时更新product的值为原来的值乘上right指向的数。
5. 如果product的值为0,说明当前连续子段的乘积为0,需要将left向右移动一位,同时重置product的值为1。
6. 将当前连续子段的乘积存储到result中。
7. 当right指向序列的结尾时,结束循环,返回result。
以下是C++代码实现:
```
#include <vector>
std::vector<int> allSubarrayProducts(std::vector<int> nums) {
int n = nums.size();
int left = 0, right = 0;
int product = 1;
std::vector<int> result;
while (right < n) {
product *= nums[right];
while (left <= right && product == 0) {
product /= nums[left];
left++;
}
result.push_back(product);
right++;
}
return result;
}
```
这段代码通过维护一个连续子段的乘积,避免了重复计算,时间复杂度为O(n)。
阅读全文