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/
題目解讀：
這道題給定了一個(gè)數(shù)組與一個(gè)target數(shù)谱秽，要求返回?cái)?shù)組中“和”小于或者等于target數(shù)的兩個(gè)數(shù)組合的個(gè)數(shù)示损。
解題方法：
首先將數(shù)組排序肌厨，然后使用頭尾指針解決兰英，當(dāng)頭尾兩個(gè)數(shù)相加大于target疯淫，尾指針向前移形帮；否則尾指針前面到頭指針?biāo)械臄?shù)與頭指針的數(shù)相加都會(huì)小于或等于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; }
