| Data | MightValue |
|---|---|
| 4 | 4 |
| 2 | 2,6 |
| -1 | -1,1,5 |
每一個(gè)值都有自己可能的取值。但是超時(shí)了，vector的更新還是太會(huì)費(fèi)時(shí)間。
注意：要用double類型，或者long long類型，因?yàn)椴煌膇nt類型相加會(huì)出現(xiàn)內(nèi)存泄漏的情況
class Solution {public: vector<double> newList(int number, vector<double> oldList,int& count,int lower,int upper) { vector<double> result; result.push_back(number); if(number<=(double)upper && number>=(double)lower) count++; for(int i=0;i<oldList.size();i++) { result.push_back(double(number)+double(oldList[i])); if(result.back()<=(double)upper && result.back()>=(double)lower) count++; } return result; } int countRangeSum(vector<int>& nums, int lower, int upper) { if(nums.size()==0) return 0; int count=0; vector<double> list; for(int i=0;i<nums.size();i++) list=newList(nums[i],list,count,lower,upper); return count; }};改進(jìn)代碼（兩種方法是一樣的，只不過這種方法避免了vector的不斷更新，而是保存了其sum） 因此采用另一種方法，這種方法利用multiset類型。 值得注意的是: multiset可以維持一個(gè)有元素重復(fù)的數(shù)組，并且數(shù)組是按照從小到大的順序自動(dòng)存儲(chǔ)。set則不允許有元素重復(fù)。map不允許key重復(fù)，不過也是安裝key值自動(dòng)從小到大排序。正確代碼采用了另一種處理思路。最主要的是不再處理原始數(shù)據(jù)，而是處理他們的sum。由于計(jì)算的區(qū)間是連續(xù)區(qū)間，所以[i,j] 區(qū)間的和就是sum[j]-sum[i]。其中有幾個(gè)特殊的地方需要注意：
當(dāng)i=0時(shí)，區(qū)間[0,j]的和就是sum[j]-sum[0]=sum[j]，因此sum[0]=0。所以一開始，數(shù)組需要先增加一個(gè)元素0。當(dāng)i=j時(shí)，區(qū)間[j,j]的和就是sum[j]-sum[j]=0。不對(duì)，需要單獨(dú)處理。class Solution {public: int countRangeSum(vector<int>& nums, int lower, int upper) { if(nums.size()==0) return 0; int count=0; multiset<double> sumSet; double sum=0; sumSet.insert(0); for(int i=0;i<nums.size();i++) { sum+=(double)nums[i]; multiset<double>::iterator itStart,itEnd; itStart=sumSet.lower_bound(sum-(double)upper); itEnd=sumSet.upper_bound (sum-(double)lower); count+=std::distance(itStart,itEnd); cout<<count<<" "; sumSet.insert(sum); } return count; }};新聞熱點(diǎn)
疑難解答
圖片精選
網(wǎng)友關(guān)注
