Lintcode - Two Sum - Less than or equal to target

Given an array of integers, find how many pairs in the array such that their sum isless than or equal toa specific target number. Please return the number of pairs.

Have you met this question in a real interview?

Yes

Example

Given nums =[2, 7, 11, 15], target =24.
Return5.
2 + 7 < 24
2 + 11 < 24
2 + 15 < 24
7 + 11 < 24
7 + 15 < 25

Analysis: the straightfoward solution by using two nesting loops is too slow O(N ^ 2). The trick is sort the array first and with the outer loop starting with ascending order and the inner loop descending.

    public int twoSum5(int[] nums, int target) {
        if (nums.length == 0){
            return 0;
        }

        Arrays.sort(nums);

        int right = nums.length;
        int count = 0;
        for (int i = 0; i < right - 1; i++){
            for (int j = right - 1; j > i; j--){
                if (nums[i] + nums[j] <= target) {
                    count += j - i;
                    right = j;
                    break;
                } 
            }
        }

        return count;
    }

this essentially is the following.

     public int twoSum5(int[] nums, int target) {
        if (nums.length == 0){
            return 0;
        }

        Arrays.sort(nums);

        int count = 0;
        int left = 0;
        int right = nums.length - 1;

        while (left < right){
            if (nums[left] + nums[right] > target){
                right--;
            } else {
                count += right - left;
                left++;
            }
        }
        return count;
    }