Re: [閒聊] 每日leetcode
忘記哪天的每日
補一下
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
推
11/16 16:59,
1年前
, 1F
11/16 16:59, 1F
推
11/16 17:09,
1年前
, 2F
11/16 17:09, 2F
討論串 (同標題文章)
完整討論串 (本文為第 1126 之 1554 篇)：