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.

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

这是Lintcode上的一道题目，可以算是Two Sum 的follow up，求两数之和超过一定值的对数。既然是超过一定的值，不是一个定值，hashmap是没法使用的，这个时候排序和two pointer就要出马了。

首先对数组进行排序。然后初始化left ＝ 0， right ＝ n-1。如果nums[right] + nums[left] > target, 则［i，right] (left =< i < right)的所有组合都符合条件，此时right在当前位置的作用已经失去了，所以right－－。反之，如果nums[right] + nums[left] <= target, 说明这个left不合格，不能找到另一数字和其匹配，left++。代码如下：

class Solution:
    # @param nums, an array of integer
    # @param target, an integer
    # @return an integer
    def twoSum2(self, nums, target):
        if not nums or len(nums) < 2:
            return 0
        nums.sort()
        left = 0
        right = len(nums) - 1
        res = 0
        while left < right:
            if nums[left] + nums[right] <= target:
                left += 1
            else:
                res += right - left 
                right -= 1
        
        return res

这种解法的时间复杂度为O(nlogn) + O(n) = O(nlogn), 空间复杂度为O(1)(就地排序的话）。