LintCode 443 [Two Sum II]

原题

给一组整数，问能找出多少对整数，他们的和大于一个给定的目标值。

样例
对于 numbers = [2, 7, 11, 15], target = 24 的情况，返回 1。因为只有11 + 15可以大于24。

解题思路

• 借鉴Two Sum的解法 - Two Pointers(对撞型指针)
• 首先数组要排序，然后i在头，j在尾
• 如果numbers[i] + numbers[j] > target，不需要考虑numbers[i+1 ~ j-1] + numbers[j]的和，因为一定也大于target，所以answer += j - i，然后j--
• 如果numbers[i] + numbers[j] <= target，不需要再考虑numbers[i]和numbers[i+1 ~ j-1]的和，因为一定小于target，所以直接i++

完整代码

class Solution:
    # @param nums, an array of integer
    # @param target, an integer
    # @return an integer
    def twoSum2(self, nums, target):
        # Write your code here
        count = 0
        if (nums == None or len(nums) == 0):
            return count
        nums.sort()
        i = 0
        j = len(nums) - 1
        while (i < j):
            if nums[i] + nums[j] <= target:
                i += 1
            elif nums[i] + nums[j] > target:
                count += j-i
                j -= 1
        return count