327. count-of-range-sum
この問題は難易度が高く、基本的にはhardの問題は頭を使わなければならないが、一般的な方法によると、和を求めて暴力を振るう複雑さはO(N^2)であり、問題ではO(N^2)がnaiveであることを明確にしているので、この問題の難点は時間の複雑さをどのように下げるかにある.
1組の数と1つの区間を与えて、組の数の中ですべてこの区間の和を満たすサブ配列の個数を変えることを求めて、配列の中から1組の連続する数を選んで、もし選んだ数の和が条件を満たすならば、1組の有効な数と見なして、もし条件を満たさないならば、無効で、すべての有効な配列の個数を求めます.
構想は、sums[i]が配列の前のi個のデータの和を表し、jからiまでの間の配列を選択してsums[i]-sums[j]と表すと仮定し、この配列はlower<=sums[i]-sums[j]<=upper、sums[i]が現在遍歴している最も遠い位置であり、sum[j]はすでに遍歴した位置であるため、すでに配列に存在している.一方sum[i]は算出されたばかりの固定値であるため,元のsums配列に一定の条件を満たすsums[j]が見つかれば,j−iは一定の条件を満たす.原式はlower<=sums[i]-sums[j]<=upperであり、sums[i]-upper<=sums[j]<=sums[i]-lowerである.
以上の解析的な考え方から明らかなように,0から遍歴を開始し,配列中の前i個の値の和に遍歴した場合,sums配列中の前i個の値のうちsums[i]−upper<=sums[j]<=sums[i]−lower(j)を満たすものがいくつかあると判断する.
以下はACコードです.
1組の数と1つの区間を与えて、組の数の中ですべてこの区間の和を満たすサブ配列の個数を変えることを求めて、配列の中から1組の連続する数を選んで、もし選んだ数の和が条件を満たすならば、1組の有効な数と見なして、もし条件を満たさないならば、無効で、すべての有効な配列の個数を求めます.
構想は、sums[i]が配列の前のi個のデータの和を表し、jからiまでの間の配列を選択してsums[i]-sums[j]と表すと仮定し、この配列はlower<=sums[i]-sums[j]<=upper、sums[i]が現在遍歴している最も遠い位置であり、sum[j]はすでに遍歴した位置であるため、すでに配列に存在している.一方sum[i]は算出されたばかりの固定値であるため,元のsums配列に一定の条件を満たすsums[j]が見つかれば,j−iは一定の条件を満たす.原式はlower<=sums[i]-sums[j]<=upperであり、sums[i]-upper<=sums[j]<=sums[i]-lowerである.
以上の解析的な考え方から明らかなように,0から遍歴を開始し,配列中の前i個の値の和に遍歴した場合,sums配列中の前i個の値のうちsums[i]−upper<=sums[j]<=sums[i]−lower(j)を満たすものがいくつかあると判断する.
以下はACコードです.
class Solution {
public:
int countRangeSum(vector& nums, int lower, int upper) {
int res = 0;
multiset numset;
numset.insert(0);
long long sum = 0;
for (int i=0; i