資料結構
網路
關係資料庫管理系統(RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法學C++中區間和的計數
假設我們有一個整數陣列nums，我們需要找到落在範圍[lower, upper]（包含上下限）內的區間和的數量。區間和S(i, j)定義為nums中從索引i到索引j（其中i ≤ j）的元素之和。
因此，如果輸入為[-3,6,-1]，lower = -2，upper = 2，則結果為2，因為區間[0,2]的和為2，區間[2,2]的和為-2。
為了解決這個問題，我們將遵循以下步驟：
- 定義一個函式mergeIt()，它將接收陣列prefix，start，mid，end，lower，upper作為引數。
- i := start，j := mid + 1
- temp := end - start + 1
- low := mid + 1，high := mid + 1
- k := 0
- 定義一個大小為temp的陣列arr。
- 當i <= mid時，執行以下操作：
- 當(low <= end 且 prefix[low] - prefix[i] < lower)時，執行以下操作：
- low自增1
- 當(high <= end 且 prefix[high] - prefix[i] <= upper)時，執行以下操作：
- high自增1
- 當(j <= end 且 prefix[j] < prefix[i])時，執行以下操作：
- arr[k] := prefix[j]
- j自增1
- k自增1
- arr[k] := prefix[i]
- i自增1
- k自增1
- count := count + high - low
- 當(low <= end 且 prefix[low] - prefix[i] < lower)時，執行以下操作：
- 當j <= end時，執行以下操作：
- arr[k] := prefix[j]
- k自增1
- j自增1
- 對於i從0到temp-1迴圈，執行以下操作：
- prefix[start] := arr[i]
- start自增1
- 定義一個函式merge()，它將接收prefix[]，start，end，lower，upper作為引數。
- 如果start >= end，則返回。
- mid := start + (end - start) / 2
- 呼叫函式merge(prefix, start, mid, lower, upper)
- 呼叫函式merge(prefix, mid + 1, end, lower, upper)
- 呼叫函式mergeIt(prefix, start, mid, end, lower, upper)
- 在主方法中，執行以下操作：
- n := nums的大小
- count := 0
- 定義一個大小為n+1的陣列prefix。
- prefix[0] := 0
- 對於i從1到n迴圈，執行以下操作：
- prefix[i] := prefix[i - 1] + nums[i - 1]
- 呼叫函式merge(prefix, 0, n, lower, upper)
- 返回count
讓我們來看下面的實現，以便更好地理解：
示例
#include <bits/stdc++.h>
using namespace std;
typedef long long int lli;
class Solution {
public:
int count = 0;
void mergeIt(lli prefix[], lli start ,lli mid, lli end, lli lower, lli upper){
lli i = start, j = mid + 1;
lli temp = end - start + 1;
lli low = mid + 1, high = mid + 1;
lli k = 0;
lli arr[temp];
while(i <= mid){
while(low <= end && prefix[low] - prefix[i] < lower) low++;
while(high <= end && prefix[high] - prefix[i] <= upper) high++;
while(j<= end && prefix[j] < prefix[i]){
arr[k] = prefix[j];
j++;
k++;
}
arr[k] = prefix[i];
i++;
k++;
count += high - low;
}
while(j <= end){
arr[k] = prefix[j];
k++;
j++;
}
for(i = 0; i < temp; i++){
prefix[start] = arr[i];
start++;
}
}
void merge(lli prefix[], lli start, lli end, lli lower, lli upper){
if(start >= end)return;
lli mid = start + (end - start) / 2;
merge(prefix, start, mid, lower, upper);
merge(prefix, mid + 1, end, lower, upper);
mergeIt(prefix, start, mid, end, lower, upper);
}
int countRangeSum(vector<int>& nums, int lower, int upper) {
lli n = nums.size();
count = 0;
lli prefix[n + 1];
prefix[0] = 0;
for(lli i = 1; i <= n; i++){
prefix[i] = prefix[i - 1] + nums[i - 1];
}
merge(prefix, 0, n, lower, upper);
return count;
}
};
main(){
Solution ob;
vector<int> v = {-3,6,-1};
cout << (ob.countRangeSum(v, -2, 2));
}輸入
{-3,6,-1}
-2
2輸出
2
更新於：2020年6月1日
508 次瀏覽
廣告