Description:

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

Example:

Given nums = [2, 7, 11, 15], target = 24.
Return 5.
2 + 7 < 24
2 + 11 < 24
2 + 15 < 24
7 + 11 < 24
7 + 15 < 25

Link:

http://www.lintcode.com/en/problem/two-sum-less-than-or-equal-to-target/

題目解讀：

這道題給定了一個數(shù)組與一個target數(shù)，要求返回數(shù)組中“和”小于或者等于target數(shù)的兩個數(shù)組合的個數(shù)。

解題方法：

首先將數(shù)組排序，然后使用頭尾指針解決，當(dāng)頭尾兩個數(shù)相加大于target，尾指針向前移；否則尾指針前面到頭指針?biāo)械臄?shù)與頭指針的數(shù)相加都會小于或等于target，所以count += end - start. 直到頭指針和尾指針相交循環(huán)結(jié)束。

Time Complexity：

O(nlogn)

完整代碼：

int twoSum5(vector<int> &nums, int target) { int count = 0; if(nums.size() < 2) return count; sort(nums.begin(), nums.end()); int start = 0, end = nums.size() - 1; while(start < end) { int temp = nums[start] + nums[end]; if(temp > target) end--; else { count += end - start; start++; } } return count; }