双指针

class Solution:
    def countPairs(self, nums: List[int], target: int) -> int:
        nums.sort()
        j = len(nums) - 1
        ans = 0
        # 遍历第一个指针，寻找满足k>i且nums[i]+nums[k]<target的k
        for i in range(len(nums) - 1):
            # 1.由于nums是递增的，如果nums[i] + nums[i + 1] >= target，
            #   后面都不会存在满足条件的k了，跳出循环；
            # 2.如果i==j,上个循环结束i=j-1且nums[i]+nums[j]<target,
            #   nums[i]+nums[j+1]>=target，所以nums[j]+nums[j+1]>=target,后面不存在满足条件的k；
            #   i>j时说明上个循环就不存在满足条件的k了
            if nums[i] + nums[i + 1] >= target or i >= j:
                break
            # 我们要让j随着i变化，j是递减的，随着j的递减，nums[i] + nums[j]会变小，
            # 所以当nums[i] + nums[j]>=target时要一直循环，
            # 保证可以找到nums[i] + nums[j] < target的临界点，这样所有小于等于j大于i的下标都满足条件
            while i < j and nums[i] + nums[j] >= target:
                j -= 1
            ans += j - i
        return ans

class Solution:
    def countPairs(self, nums: List[int], target: int) -> int:
        nums.sort()
        i = 0
        ans = 0
        # 遍历第二个指针,寻找满足k<j且nums[k]+nums[j]<target的k
        for j in range(len(nums) - 1, 0, -1):
            # 1.这里不会有提前退出的机制，因为j是循环递减的，nums[j]也是循环递减的，
            #   因此循环次数越多，越容易找到满足条件的i
            # 2.如果i>=j，说明所有小于j的下标都是满足要求的，不能退出，此时满足条件的下标一共i个

            # 我们要让i随着j变化，i是递增的，随着i的递减，nums[i] + nums[j]会变大，
            # 所以当nums[i] + nums[j]<target时要一直循环，
            # 保证可以找到nums[i] + nums[j] >= target的临界点，这样所有小于i的下标都满足条件
            while i < j and nums[i] + nums[j] < target:
                i += 1
            # i>=j和i<j的情况合并之后，ans+=min(i,j)
            ans += min(i, j)
        return ans