leetcode-2563

题目

题目链接

分析

• lower <= nums[i] + nums[j] <= upper
• 0<=i<j<n
• 则i,j 是公平数对
• 排序双指针，两个指针每次从上次的位置偏移即可
  • 每次确定i，遍历所有数字作为i O(n)
  • left记为lower <= nums[i] + nums[j]的第一个j
  • right记为nums[i] + nums[j] > upper的第一个j
  • 每个i对应的j的数量为 j-i
  • 随着i增大，left和right必然左移（nums[j]减小）
  • 如果i位于 left right中间，要减去（i，j不相同）
  • 注意right的边界（可能为n注意越界）

源代码

源代码