思路
需要满足, 0 <= i < j < n
且nums[i] + nums[j] < target
。这里我们可以先拍一个序,拍序之后数组就是一个有序的。使用双向双指针。
当left + right < target
那么就说明,right
指针左边的所有数都是符合条件的,因此就可以将ans += right - left
。因为是有序的,所以说移动left
指针,right
指针是不需要考虑向后移动的。
同理如果left + right >= target
那么将右指针进行移动
代码
class Solution {
public int countPairs(List<Integer> nums, int target) {
int n = nums.size();
Collections.sort(nums);
int ans = 0;
int left = 0;
int right = n - 1;
while (left < right) {
if (nums.get(left) + nums.get(right) < target) {
ans += right - left;
left++;
} else {
right--;
}
}
return ans;
}
}