# Two Sum II

## 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.

Tags

Two Pointers Sort

## Analysis

1. 先对数组排序，时间复杂度为O(nlogn)
2. 初始化left = 0, right = nums.length - 1，如果有一个满足nums[left] + nums[right] > target, 那么对于left ~ right - 1，都会满足条件，因此计入结果中，count = count + right - left。循环结束的条件是 left < right 不被满足，说明两个指针相遇，所有的情况都被遍历。这一个过程的时间复杂度是 O(n)。

## Solution

``````public class Solution {
/**
* @param nums: an array of integer
* @param target: an integer
* @return: an integer
*/
public int twoSum2(int[] nums, int target) {
// Invalid input or exception
if (nums == null || nums.length == 0) {
return 0;
}

// Sort the Array nums[] to ascending order
Arrays.sort(nums);

// Use two pointers
int count = 0;
int pl = 0;
int pr = nums.length - 1;

while (pl < pr) {
if (nums[pl] + nums[pr] > target) {

// Index from pl to pr - 1 will all be counted
count = count + (pr - pl);
pr--;
} else {
pl++;
}
}
return count;
}
}
``````