Skip to content
Blogster on GitHub Dinesh on Twitter

2824.统计和小于目标的下标对数目

链接

思路

需要满足, 0 <= i < j < nnums[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;

    }
}