題目：Count of Range Sum

Given an integer array?nums, return the number of range sums that lie in?[lower, upper]?inclusive.
Range sum?S(i, j)?is defined as the sum of the elements in?nums?between indices?i?and?j?(i?≤?j), inclusive.

Note:
A naive algorithm of?O(n2) is trivial. You MUST do better than that.

Example:
Given?nums?=?[-2, 5, -1],?lower?=?-2,?upper?=?2,
Return?3.
The three ranges are :?[0, 0],?[2, 2],?[0, 2]?and their respective sums are:?-2, -1, 2.

題意：

給定一個整數數組和一個范圍，找到該數組的子集(要求子集是數組中連續的數)中滿足子集元素的和在給定范圍內的所有子集的個數。

分析：

正常的思路，需要找數組的不同的子集，復雜度為O(n^2)。

/** 動態規劃：S[i][j]表示nums中從i到j的和 S[i][j] = S[i][j - 1] + nums[j] **/ int LeetCode::countRangeSum(vector<int>& nums, int lower, int upper){int n = nums.size();vector<vector<int>> sum(n,vector<int>(n, 0));int count = 0;for (size_t i = 0; i < n; i++){sum[i][i] = nums[i];if (sum[i][i] >= lower && sum[i][i] <= upper)++count;}for (size_t i = 0; i < n; i++){for (size_t j = i + 1; j < n; j++){sum[i][j] = sum[i][j - 1] + nums[j];if (sum[i][j] >= lower && sum[i][j] <= upper)++count;}}return count; }

但是，它可以在O(nlogn)的復雜度中完成。

設S(n)表示前n個元素的和，SubSet(i,j)表示數組i到j的子集的和；給定的范圍是[low,up]；

則簡單來講，要找滿足low<=SubSet(i,j)<=up的SubSet的個數。

SubSet(i,j) = S(j) - S(i);也就是要求low<=S(j) - S(i)<=up中ij的個數。

這是可以看出必然需要一個輔助數組保存前n個元素的和；

簡化要求來思考：當訪問到新的元素j時，得到前j項和，則此時如果是只需求以j為終點的子集中滿足題目要求的和的子集個數該怎么求呢？

只需要遍歷前j-1個前n項和然后用S(j)-S(k)，判斷是否在范圍內即可；

進一步，如果前j-1個前n項和是有序的，就只要找到第一個滿足下界和最后一個滿足上界的，然后他們之間包含多少個元素就有多少個滿足要求的子集。

這樣就要求按大小順序來存儲前n項和，而且可以使用lower_bound()和upper_bound()函數來確定范圍，于是就可以想到用multiset來存儲前n項和。

那么要找到所有的數組中子集滿足條件的個數，就需要將上面求的每個位置的子集的數量加起來即可。

/** 一個基本的想法是使用multiset保存前i個元素的和.因為set是有序的可重復的容器. 當前位置為i時的滿足給定范圍的序列應該是：lower=< sum[i]-sum[j]<= upper.它對應的范圍是[j,i]. 所以只需要計算j的個數：使得j (0=< j< i) 滿足 sum[i]-upper=< sum[j]<= sum[i]-lower. STL提供的函數upper_bound, lower_bound能夠快速找到這樣的j的范圍，因為set有序范圍內的一定滿足上面的條件. set使用紅黑樹來實現，因此上面的操作時間復雜度O(logN). 所以總的時間復雜度為O(NlogN). **/ int LeetCode::countRangeSum(vector<int>& nums, int lower, int upper){multiset<long long>sums;//注意使用long long防止溢出long long sum = 0L;int result = 0;sums.insert(0);//插入第0個和for (size_t i = 0; i < nums.size(); i++){sum += nums[i];result += distance(sums.lower_bound(sum - upper), sums.upper_bound(sum - lower));//找到滿足sum[i]-upper=< sum[j]<= sum[i]-lower的范圍 sums.insert(sum);}return result; }

?

轉載于:https://www.cnblogs.com/yeqluofwupheng/p/6959377.html

總結

以上是生活随笔為你收集整理的[LeetCode]Count of Range Sum的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。