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.

Example:

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

Solution:

Similar to standard Two Sum. We can use two pointers to find the pairs that their sum is bigger than target. If we find sum of one pair is greater than target, the sum of any pair between left and right is also greater than target.

Code:

public class Solution {
    public int twoSum2(int[] nums, int target) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        int result = 0;
        Arrays.sort(nums);
        int left = 0;
        int right = nums.length - 1;
        while (left < right) {
            int num = nums[left] + nums[right];
            if (num > target) {
                result = result + (right - left);
                right--;
            } else {
                left++;
            }
        }
        return result;
    }
}