LeetCode 解題紀錄 2563. Count the Number of Fair Pairs

LeetCode - The World's Leading Online Programming Learning Platform

題目

給定一個整數陣列 nums，以及兩個整數 lower 和 upper，要求返回 fair pairs 數目。fair pairs 是兩個索引位置 i，j 其中 i < j 且 lower ≤ nums[i]+nums[j] ≤ upper

條件

• 1 ≤ nums.length ≤ 10⁵
• nums.length = n
• -10⁹ ≤ nums[i] ≤ 10⁹
• -10⁹ ≤ lower, upper ≤ 10⁹

觀察

• 計算符合某個區間條件數目時，可以先計算小於上限的總數再減去小於下限的總數
• 當排序後，一個區段的開始與結束值相加不大於上限時，區段中第一個數字加上區段中的任意數字都不會大於上限

解法(Sort + Sliding Window)

• 先將數字排序
• 計算小於上限的總數再減去小於下限減 1 的總數

class Solution {
    public long countFairPairs(int[] nums, int lower, int upper) {
        Arrays.sort(nums);
        int n = nums.length;
        return countLess(nums, upper)-countLess(nums, lower-1);
    }
    long countLess(int nums[], int target) {
        long res = 0l;
        // 使用兩個指標，左指標每次移動一個位置
        for(int left=0, right=nums.length-1;left<right;left++) {
            // 持續移動右指標直到相加小於 target 值, target 可能是負數
            // 要檢查 right > left 
            while(left < right && nums[left]+nums[right] > target) 
                right--;            
            // 加上 window 大小(第一個數字配上剩下的數字)
            res += right-left;
        }
        return res;
    }
}

結果

TC：O(n*log n)

SC：O(1)