Thursday, March 30, 2017

Two Sum - Less than or equal to target

Given an array of integers, find how many pairs in the array such that their sum is less than or equal to a specific target number. Please return the number of pairs.
When the left number is fixed, find the largest number whose sum is smaller or equal to the target.

public class Solution {
    /**
     * @param nums an array of integer
     * @param target an integer
     * @return an integer
     */
    public int twoSum5(int[] nums, int target) {
        // Write your code here
        int count = 0;
        if (nums == null || nums.length == 0) return count;
        Arrays.sort(nums);
        //[2, 7, 11, 15]
        //    l       r
        int l = 0;
        int r = nums.length - 1;
        //we want to fix l and scan the r pointer
        while (l < r) {
            //r is as large as possible
            if (nums[l] + nums[r] <= target) {
                count += r - l;
                l++;
            } else {
                r--;
            }
        }
        return count;
    }
}

No comments:

Post a Comment