# 力扣 leetcode 795. 区间子数组个数()-其他

## 力扣 leetcode 795. 区间子数组个数()

### 问题描述

``nums``
``left``
``right``
``nums``
``[left, right]``

``32-bit``

• 1 <= nums.length <= 10^5
• 0 <= nums[i] <= 10^9
• 0 <= left <= right <= 10^9

### 示例1：

``````输入：nums = [2,1,4,3], left = 2, right = 3

``````

### 示例2：

``````输入：nums = [2,9,2,5,6], left = 2, right = 8

``````

### 解体思路

``right``

``nums = [2, 9, 2, 5, 6], left = 3, right = 8``
``right``
``[2], [2, 5, 6]``
• 遍历子数组中每一个元素，如果该元素大于等于left，则该元素可以与后面的所有元素组成满足条件的子数组。
• 如果该元素小于left，则它可以与后面的第一个大于等于left的元素共同组成满足条件的子数组。

。我们先遍历，发现所有元素小于的子数组为：。计算包含的子数组的个数：

``nums = [1, 2, 3, 4, 6], left = 3, right = 5``
``nums``
``right``
``sub = [1, 2, 3, 4]``
``nums[i]``
• i = 0时，nums[i] < left，记录此时小于left的元素的个数tmp = 1
• i = 1时，nums[i] < left，记录此时小于left的元素的个数tmp = 2
• i = 2时，nums[i] = left，满足条件的子数组个数为：cnt = sub.size() – i，此外，nums[0]和nums[1]也可以与num[2]组成满足条件的子数组，个数也是sub.size() – i，令tmp = 0
• i = 3时，nums[i] > left，满足条件的子数组个数为：cnt = sub.size() – i

``total = (sub.size() - 2) * 3 + (sub.size() - 3) = 7``

``````class Solution {
public:
int numSubarrayBoundedMax(vector<int>& nums, int left, int right) {
int cnt = 0;
int start_index = 0;
int tmp = 0;
for(int i = 0; i < nums.size(); i++){
if(nums[i] > right){
if(nums[start_index] <= right){
tmp = 0;
for(int j = start_index; j < i; j++){
if(nums[j] >= left){
cnt = tmp == 0 ? (cnt + i - j) : (cnt + (i - j) * (tmp + 1));
tmp = 0;
}
else{
tmp += 1;
}
}
}
start_index = i + 1;
}
}
if(start_index < nums.size()){
tmp = 0;
for(int i = start_index; i < nums.size(); i++){
if(nums[i] >= left){
cnt = tmp == 0 ? (cnt + nums.size() - i) : (cnt + (nums.size() - i) * (tmp + 1));
tmp = 0;
}
else{
tmp += 1;
}
}
}
return cnt;
}
};
``````
————————

### 问题描述

``nums``
``left``
``right``
``nums``
``[left, right]``

``32-bit``

• 1 <= nums.length <= 10^5
• 0 <= nums[i] <= 10^9
• 0 <= left <= right <= 10^9

### 示例1：

``````输入：nums = [2,1,4,3], left = 2, right = 3

``````

### 示例2：

``````输入：nums = [2,9,2,5,6], left = 2, right = 8

``````

### 解体思路

``right``

``nums = [2, 9, 2, 5, 6], left = 3, right = 8``
``right``
``[2], [2, 5, 6]``
• 遍历子数组中每一个元素，如果该元素大于等于left，则该元素可以与后面的所有元素组成满足条件的子数组。
• 如果该元素小于left，则它可以与后面的第一个大于等于left的元素共同组成满足条件的子数组。

。我们先遍历，发现所有元素小于的子数组为：。计算包含的子数组的个数：

``nums = [1, 2, 3, 4, 6], left = 3, right = 5``
``nums``
``right``
``sub = [1, 2, 3, 4]``
``nums[i]``
• i = 0时，nums[i] < left，记录此时小于left的元素的个数tmp = 1
• i = 1时，nums[i] < left，记录此时小于left的元素的个数tmp = 2
• i = 2时，nums[i] = left，满足条件的子数组个数为：cnt = sub.size() – i，此外，nums[0]和nums[1]也可以与num[2]组成满足条件的子数组，个数也是sub.size() – i，令tmp = 0
• i = 3时，nums[i] > left，满足条件的子数组个数为：cnt = sub.size() – i

``total = (sub.size() - 2) * 3 + (sub.size() - 3) = 7``

``````class Solution {
public:
int numSubarrayBoundedMax(vector<int>& nums, int left, int right) {
int cnt = 0;
int start_index = 0;
int tmp = 0;
for(int i = 0; i < nums.size(); i++){
if(nums[i] > right){
if(nums[start_index] <= right){
tmp = 0;
for(int j = start_index; j < i; j++){
if(nums[j] >= left){
cnt = tmp == 0 ? (cnt + i - j) : (cnt + (i - j) * (tmp + 1));
tmp = 0;
}
else{
tmp += 1;
}
}
}
start_index = i + 1;
}
}
if(start_index < nums.size()){
tmp = 0;
for(int i = start_index; i < nums.size(); i++){
if(nums[i] >= left){
cnt = tmp == 0 ? (cnt + nums.size() - i) : (cnt + (nums.size() - i) * (tmp + 1));
tmp = 0;
}
else{
tmp += 1;
}
}
}
return cnt;
}
};
``````