Two Sum II

题目：

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.

分析：

这是算法提高班的第一题，说起来蛮有意义的。

这道题目有个提示叫做用O(nlogn)的复杂度来完成，如果给这个提示则可以想到需要排序。那么排序之后怎么做呢？使用了一个two pointer的思想：

    1, 2, 3, 4, 5
1,              6
2,              7
3,              8
4,              9
5               ...

可以看出，开始让start = 0, end = size - 1, 如果start + end > target则说明end和任意组合，都满足>target, 这时候给count+=(end - start)然后end--。

一直到出现这种情况：1 + 3 = 4，不满足>target, 这时候需要start++了，并且count保持不变。

    1, 2, 3, 4, 5
1,        4      
2,              
3,              
4,              
5

给以个while(start < end)则可以保证循环不超过O(n)。

解法：

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
        if (nums.size() <= 1) {
            return 0;
        }
        sort(nums.begin(), nums.end() );
        int start = 0;
        int end = nums.size() - 1;
        int count = 0;
        while (start < end) {
            if (nums[start] + nums[end] > target) {
                count += end - start;
                end--;
            } else {
                start++;
            }
        }
        return count;
    }
};