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

与two sum问题相比，因为是“大于”的关系比较，因此用Hashmap不能达到记忆化查找的效果。这里用two pointers的思路求解则十分简明： 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;
    }
}