609. Two Sum - Less than or equal to target

描述

给定一个整数数组，找出这个数组中有多少对的和是小于或等于目标值。返回对数。

样例

给定数组为 [2,7,11,15]，目标值为 24
返回 5。
2+7<24
2+11<24
2+15<24
7+11<24
7+15<24

思路

同上面两数之和大于target的follow up类似，只是固定端变成了左指针

代码

public class Solution {
    /*
     * @param nums: an array of integer
     * @param target: an integer
     * @return: an integer
     */
    public int twoSum5(int[] nums, int target) {
        if (nums == null && nums.length < 2) {
            return 0;
        }
        Arrays.sort(nums);
        int left = 0, right = nums.length - 1;
        int count = 0;
        while (left < right) {
            int sum = nums[left] + nums[right];
            if (sum > target) {
                right--;
            } else {
                //这两行语句顺序不能颠倒，因为left变化会影响count值
                count += right - left;
                left++;
            }
        }
        return count;
    }    
}