Problem
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.
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.
Solution
Two Pointers的思想，先排序数组。如果a[i] + a[j] > target, 说明 a[i..j]之间的数的和都大于target所以只要累加j-i个数就行了，之后j--，继续寻找。
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
sort(nums.begin(), nums.end());
int i = 0;
int j = nums.size() - 1;
int count = 0;
while (i < j) {
int sum = nums[i] + nums[j];
if (sum > target) {
count += j - i;
j--;
} else {
i++;
}
}
return count;
}
};
