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
思路
- 把数组排序。
- 先把首尾相加,如果小于等于target,就说明每个数和第一个数相加都是小于target的,这个时候count += end - start。且此时start++ 继续进行计算。
- 如果大于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;
}
}
推荐阅读
-
Two Sum - Less than or equal to target
-
【LeetCode 1292】 Maximum Side Length of a Square with Sum Less than or Equal to Threshold
-
1292. Maximum Side Length of a Square with Sum Less than or Equal to Threshold
-
【Lintcode】609. Two Sum - Less than or equal to target
-
LeetCode-1292. Maximum Side Length of a Square with Sum Less than or Equal to Threshold
-
[leetcode] 1292. Maximum Side Length of a Square with Sum Less than or Equal to Threshold
-
Find all factorial numbers less than or equal to N
-
Maximum Side Length of a Square with Sum Less than or Equal to Threshold
-
Two Sum - Closest to target
-
Two Sum - Greater Than Target