Given an array of integers, find how many pairs in the array such that their sum is bigger than a specific target number. Please return the number of pairs.

Have you met this question in a real interview?

Yes

Example

Given numbers =[2, 7, 11, 15], target =24. Return1. (11 + 15 is the only pair)

Challenge

Do it in O(1) extra space and O(nlogn) time.

class Solution {
public:
    /**
     * @param nums: an array of integer
     * @param target: an integer
     * @return: an integer
     */
    int twoSum2(vector<int> &nums, int target) {
        // Write your code here
        int cnt = 0 ;
        sort(nums.begin(),nums.end());
        int i = 0, j = nums.size()-1;
        while(i<j){
            if(nums[i]+nums[j]>target){
                cnt+=(j-i);
                --j;
            }else{
                ++i;
            }
        }
        return cnt;
    }
};