My Simple Solution Using Binary Search


  • 2
    G
    class Solution {
    public:
    	int countRangeSum(vector<int>& nums, int lower, int upper) {
    		vector<pair<long long,int> > ps;
    		long long s = 0;
    		ps.push_back(make_pair(0, -1));
    		for(int i=0; i<nums.size(); ++i){
    			s+=nums[i];
    			ps.push_back(make_pair(s, i));
    		}
    		sort(ps.begin(), ps.end());
    
    		int ans = 0;
    		for(int i=0; i<ps.size(); ++i){
    			pair<long long,int> pp(ps[i].first + lower, 0);
    			int x1 = lower_bound(ps.begin(), ps.end(), pp)- ps.begin();
    			pp = make_pair(ps[i].first+upper, ps.size());
    			int x2 = upper_bound(ps.begin(), ps.end(), pp)- ps.begin();
    			for(int j=x1; j<x2; ++j){
    				if(ps[j].second > ps[i].second)
    					++ans;
    			}
    		}
    
    		return ans;
    	}
    };

  • 3
    P

    The inner loop makes it O(n^2)


  • 0
    G

    You are right. And I find that replace the binary search phase by binary index tree can make it O(nlogn) .


  • 0
    C

    I'm curiosity about how to solve the badest situaction ,because we need the second element of the pair.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.