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

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

• 难度: easy
• 原始链接: https://leetcode.cn/problems/count-pairs-whose-sum-is-less-than-target
• 标签: 排序, 二分

解法一: 枚举

go

func countPairs(nums []int, target int) int {
    ans := 0
    length := len(nums)
    for i := 0; i < length; i++ {
        for j := i + 1; j < length; j++ {
            if nums[i] + nums[j] < target {
                ans++
            }
        }
    }
    return ans
}

解法二: 排序, 二分

go

func countPairs(nums []int, target int) int {
    sort.Ints(nums)
    ans := 0
    length := len(nums)
    for i := 0; i < length; i++ {
        left := i
        right := length - 1
        curTarget := target - nums[i]
        for left < right {
            mid := ((right - left + 1) >> 1) + left
            if nums[mid] >= curTarget {
                right = mid - 1
            } else {
                left = mid
            }
        }
        ans += left - i
    }
    return ans
}