Given a 0-indexed integer array nums
of size n
and two integers lower
and upper
, return the number of fair pairs.
A pair (i, j)
is fair if:
0 <= i < j < n
, andlower <= nums[i] + nums[j] <= upper
Example 1:
Input: nums = [0,1,7,4,4,5], lower = 3, upper = 6 Output: 6 Explanation: There are 6 fair pairs: (0,3), (0,4), (0,5), (1,3), (1,4), and (1,5).
Example 2:
Input: nums = [1,7,9,2,5], lower = 11, upper = 11 Output: 1 Explanation: There is a single fair pair: (2,3).
Constraints:
1 <= nums.length <= 105
nums.length == n
-109 <= nums[i] <= 109
-109 <= lower <= upper <= 109
Solution: Two Pointers
Sort the array, use two pointers to find how # of pairs (i, j) s.t. nums[i] + nums[j] <= limit.
Ans = count(upper) – count(lower – 1)
Time complexity: O(n)
Space complexity: O(1)
C++
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
// Author: Huahua class Solution { public: long long countFairPairs(vector<int>& nums, int lower, int upper) { sort(begin(nums), end(nums)); auto count = [&](int limit) -> long long { long long ans = 0; for (int i = 0, j = nums.size() - 1; i < j; ++i) { while (i < j && nums[i] + nums[j] > limit) --j; ans += j - i; } return ans; }; return count(upper) - count(lower - 1); } }; |
请尊重作者的劳动成果,转载请注明出处!花花保留对文章/视频的所有权利。
如果您喜欢这篇文章/视频,欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
Be First to Comment