Two Sum II 443

Question

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.

Example

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

Challenge

Do it in O(1) extra space and O(nlogn) time.

Solution

原理和two sum一样，用前后指针。

1. 若前指针和后指针之和小于target，则增大前指针，

2. 若前指针和后指针之和大于target，则前指针和前后指针之间的所有数与后指针之和都大于target，将这段pair数加入sum，再减小后指针

3. 重复1－2直到两个指针相遇

代码如下：

public class Solution {
    /**
     * @param nums: an array of integer
     * @param target: an integer
     * @return: an integer
     */
    public int twoSum2(int[] nums, int target) {
        // Write your code here
        if(nums == null || nums.length == 0){
            return 0;
        }

        Arrays.sort(nums);

        int sum = 0;
        int i = 0;
        int j = nums.length - 1;
        while(i < j){
            if(nums[i] + nums[j] <= target){
                i++;
            }else{
                sum += j - i;
                j--;
            }
        }

        return sum;
    }
}