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