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)

/*

The naive way is to use two for-loops to iterate every two-element pair and compute if the sum is bigger than the target.

time: O(n^2), space:O(1)

The better way is to use two pointers. 

time:O(nlogn), space:O(1)

*/

public class Solution {

    public int twoSum2(int[] nums, int target) {

        if (nums == null || nums.length == 0) {

            return 0;

        }

        Arrays.sort(nums);

        int left = 0;

        int right = nums.length - 1;

        int count = 0;

        while (left < right) {

            if (nums[left] + nums[right] <= target) {

                left++;

            } else {

                count += right - left;

                right--;

            }

        }

        return count;

    }

}