class Solution {
public:
int countPairs(vector<int>& nums, int target) {
}
};
6954. 统计和小于目标的下标对数目
给你一个下标从 0 开始长度为n 的整数数组 nums 和一个整数 target ，请你返回满足 0 <= i < j < n 且 nums[i] + nums[j] < target 的下标对 (i, j) 的数目。
示例 1：
输入：nums = [-1,1,2,3,1], target = 2 输出：3 解释：总共有 3 个下标对满足题目描述： - (0, 1) ，0 < 1 且 nums[0] + nums[1] = 0 < target - (0, 2) ，0 < 2 且 nums[0] + nums[2] = 1 < target - (0, 4) ，0 < 4 且 nums[0] + nums[4] = 0 < target 注意 (0, 3) 不计入答案因为 nums[0] + nums[3] 不是严格小于 target 。
示例 2：
输入：nums = [-6,2,5,-2,-7,-1,3], target = -2 输出：10 解释：总共有 10 个下标对满足题目描述： - (0, 1) ，0 < 1 且 nums[0] + nums[1] = -4 < target - (0, 3) ，0 < 3 且 nums[0] + nums[3] = -8 < target - (0, 4) ，0 < 4 且 nums[0] + nums[4] = -13 < target - (0, 5) ，0 < 5 且 nums[0] + nums[5] = -7 < target - (0, 6) ，0 < 6 且 nums[0] + nums[6] = -3 < target - (1, 4) ，1 < 4 且 nums[1] + nums[4] = -5 < target - (3, 4) ，3 < 4 且 nums[3] + nums[4] = -9 < target - (3, 5) ，3 < 5 且 nums[3] + nums[5] = -3 < target - (4, 5) ，4 < 5 且 nums[4] + nums[5] = -8 < target - (4, 6) ，4 < 6 且 nums[4] + nums[6] = -4 < target
提示：
1 <= nums.length == n <= 50-50 <= nums[i], target <= 50原站题解
rust 解法, 执行用时: 0 ms, 内存消耗: 2.1 MB, 提交时间: 2023-09-12 11:43:19
impl Solution {
pub fn count_pairs(nums: Vec<i32>, target: i32) -> i32 {
let mut nums = nums;
nums.sort();
let (mut ans, mut left, mut right): (usize, usize, usize) = (0, 0, nums.len() - 1);
while left < right {
if nums[left] + nums[right] < target {
ans += right - left;
left += 1;
} else {
right -= 1;
}
}
return ans as i32;
}
}
typescript 解法, 执行用时: 76 ms, 内存消耗: 43.9 MB, 提交时间: 2023-09-12 10:18:55
function countPairs(nums: number[], target: number): number {
let res = 0, n = nums.length
for(let i = 0; i < n - 1; i++) {
for(let j = i + 1; j < n; j++) {
if(nums[i] + nums[j] < target) res++
}
}
return res
};
cpp 解法, 执行用时: 12 ms, 内存消耗: 20 MB, 提交时间: 2023-09-12 10:18:38
class Solution {
public:
int countPairs(vector<int> &nums, int target) {
sort(nums.begin(), nums.end());
int ans = 0, left = 0, right = nums.size() - 1;
while (left < right) {
if (nums[left] + nums[right] < target) {
ans += right - left;
left++;
} else {
right--;
}
}
return ans;
}
};
java 解法, 执行用时: 2 ms, 内存消耗: 40.1 MB, 提交时间: 2023-09-12 10:17:34
class Solution {
public int countPairs(List<Integer> nums, int target) {
Collections.sort(nums);
int ans = 0, left = 0, right = nums.size() - 1;
while (left < right) {
if (nums.get(left) + nums.get(right) < target) {
ans += right - left;
left++;
} else {
right--;
}
}
return ans;
}
}
javascript 解法, 执行用时: 68 ms, 内存消耗: 42.9 MB, 提交时间: 2023-09-12 10:16:57
/**
* @param {number[]} nums
* @param {number} target
* @return {number}
*/
var countPairs = function (nums, target) {
nums.sort((a, b) => a - b);
let ans = 0, left = 0, right = nums.length - 1;
while (left < right) {
if (nums[left] + nums[right] < target) {
ans += right - left;
left++;
} else {
right--;
}
}
return ans;
};
php 解法, 执行用时: 16 ms, 内存消耗: 19.1 MB, 提交时间: 2023-09-12 10:16:01
class Solution {
/**
* @param Integer[] $nums
* @param Integer $target
* @return Integer
*/
function countPairs($nums, $target) {
sort($nums);
$ans = 0;
$left = 0;
$right = count($nums)-1;
while ( $left < $right ) {
if ( $nums[$left] + $nums[$right] < $target ) {
$ans += $right - $left;
$left++;
} else {
$right--;
}
}
return $ans;
}
}
golang 解法, 执行用时: 4 ms, 内存消耗: 2.5 MB, 提交时间: 2023-08-21 09:33:40
func countPairs(nums []int, target int) (ans int) {
sort.Ints(nums)
left, right := 0, len(nums)-1
for left < right {
if nums[left]+nums[right] < target {
ans += right - left
left++
} else {
right--
}
}
return
}
python3 解法, 执行用时: 36 ms, 内存消耗: 16.2 MB, 提交时间: 2023-08-21 09:33:22
class Solution:
def countPairs(self, nums: List[int], target: int) -> int:
nums.sort()
ans = left = 0
right = len(nums) - 1
while left < right:
if nums[left] + nums[right] < target:
ans += right - left
left += 1
else:
right -= 1
return ans
python3 解法, 执行用时: 52 ms, 内存消耗: 16.1 MB, 提交时间: 2023-08-21 09:32:45
class Solution:
def countPairs(self, nums: List[int], target: int) -> int:
n, ans = len(nums), 0
nums.sort()
for i in range(0, n-1):
for j in range(i+1, n):
if nums[i] + nums[j] < target:
ans += 1
else:
break
return ans
python3 解法, 执行用时: 48 ms, 内存消耗: 15.9 MB, 提交时间: 2023-08-21 09:30:31
class Solution:
def countPairs(self, nums: List[int], target: int) -> int:
n, ans = len(nums), 0
for i in range(0, n-1):
for j in range(i+1, n):
if nums[i] + nums[j] < target:
ans += 1
return ans