Re: [閒聊] 每日leetcode

[JIWP (神楽めあ的錢包)]

忘記哪天的每日

補一下

2563. Count the Number of Fair Pairs

給一個array : nums，長度為n

再給兩個數字lower、upper

從array中任意選兩個數字nums[i]、nums[j]

這兩個數字要滿足 lower<=nums[i]+nums[j]<upper

請問這樣的組合有幾組?

思路:

先將nums進行排序

在建立一個count function

作用是找出nums中兩個數字總和小於target的組合有幾組

在count function中

令l=0、r=nums.length-1

如果nums[l]+nums[r]<target，l就+1

且回傳值加上r-l

如果nums[l]+nums[r]>=target，r就-1

這樣count function就完成了

接著回傳count(upper+1)-count(lower)就是答案

golang code :

func countFairPairs(nums []int, lower int, upper int) int64 {
        slices.Sort(nums)
        return int64(count(upper+1, nums) - count(lower, nums))
}
func count(target int, nums []int) int {
        l, r, res := 0, len(nums)-1, 0
        for r > l {
                sum := nums[l] + nums[r]
                if sum >= target {
                        r--
                } else {
                        res+=r-l
                        l++
                }
        }
        return res
}

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 42.72.99.213 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1731747181.A.6FF.html
推 sustainer123: 來台北還刷題 太卷了
推 DJYOMIYAHINA: 卷死我了