欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

Two Sum - Less than or equal to target

程序员文章站 2024-03-06 22:18:20
...

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.

Example

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

思路

  1. 把数组排序。
  2. 先把首尾相加,如果小于等于target,就说明每个数和第一个数相加都是小于target的,这个时候count += end - start。且此时start++ 继续进行计算。
  3. 如果大于target,就说明最后一个数太大了,end--。
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
        if (nums == null || nums.length == 0) {
            return 0;
        }
        
        int start = 0;
        int end = nums.length - 1;
        int count = 0;

        Arrays.sort(nums);
        while (start < end) {
            if (nums[start] + nums[end] > target) {
                end--;
            } else {
                count = count + (end - start);
                start++;
            }
        }
        return count;
    }
}