thảo luận Leetcode mỗi ngày

class Solution {
    public long countFairPairs(int[] nums, int lower, int upper) {
        long ans = 0;
        Arrays.sort(nums);
        for (int i = 0; i < nums.length; i++) {
            int l = binSearch(nums, i + 1, nums.length - 1, lower - nums[i]);
            int u = binSearch(nums, i + 1, nums.length - 1, upper - nums[i] + 1);
            ans += (u - l);
        }
        return ans;
    }

    private int binSearch(int[] nums, int l, int r, int target) {
        while (l <= r) {
            int m = l + ((r - l) >> 1);
            if (nums[m] >= target) r = m - 1;
            else l = m + 1;
        }
        return l;
    }
}

var countFairPairs = function (nums, lower, upper) {
    nums.sort((u, v) => u - v);
    const n = nums.length;
    let ans = 0;
    for (let i = 1; i < n; i++) {
        const l = _.clamp(_.sortedIndex(nums, lower - nums[i]), i);
        const r = _.clamp(_.sortedLastIndex(nums, upper - nums[i]), i);
        ans += r - l;
    }
    return ans;
};

class Solution {
public:
    long long countFairPairs(vector<int>& nums, int lower, int upper) {
        sort(nums.begin(), nums.end());
        int n = nums.size();
        long long res = 0;
        for (int i=0, l=n, r=n-1; i<n; ++i) {
            while (l>i && nums[i] + nums[l-1] >= lower) --l;
            while (r>i && nums[i] + nums[r] > upper) --r;

            if (r == i) {
                break;
            }
            if (l == n) {
                continue;
            }
            res += (r - max(i+1, l)) + 1;
        }
        return res;
    }
};

class Solution {
    public long countFairPairs(int[] nums, int lower, int upper) {
        int n = nums.length;
        Arrays.sort(nums);
        int l =1;
        int r = n-1;
        long res =0;
        for(int i =0 ;i<n-1;i++){
            if(i>=r) break;
            while(r>i &&nums[r]>upper-nums[i]){
                r--;
            }
            l=i+1;
            while(l<=r && nums[l]<lower -nums[i]){
                l++;
            }
            res+=r-l+1;
        }
        return res;
    }
  
}

class Solution {
public:
    int countSubarrays(vector<int>& nums, int k) {
        int index = find(nums.begin(), nums.end(), k) - nums.begin();
        unordered_map<int, int> diff_counter;

        for (int i=index+1, diff=0; i<nums.size(); ++i) {
            if (nums[i] < k) {
                --diff;
            } else {
                ++diff;
            }
            ++diff_counter[diff];
        }
        ++diff_counter[0];

        int res = 0;
        for (int i=index, diff = 0; i>=0; --i) {
            if (nums[i] < k) {
                --diff;
            } else if (nums[i] > k) {
                ++diff;
            }
            res += diff_counter[-diff];
            res += diff_counter[-diff+1];
        }

        return res;
    }
};

func countFairPairs(nums []int, lower, upper int) int64 {
    sort.Ints(nums)
    return countBs(nums, upper) - countBs(nums, lower - 1)
}

func countBs(nums []int, target int) int64 {
    rs, n := int64(0), len(nums)
    for l, r := 0, n-1; l < n - 1; l++ {
        if r < l + 1 { r = l + 1 }
        for l < r && nums[l] + nums[r] > target { r-- }
        rs += int64(r - l)
    }
    return rs
}

class Solution {
public:
    long long countFairPairs(vector<int>& nums, int lower, int upper);
};

using llong = long long;

llong getLower(vector<int>& arr, int value, llong low, llong high) {
    while (low < high) {
        llong mid = low + (high - low) / 2;
        if (arr[mid] < value)
            low = mid + 1;
        else
            high = mid;
    }
    if (arr[low] >= value)
        return low;
    return arr.size();
}

llong getUpper(vector<int>& arr, int value, llong low, llong high) {
    while (low < high) {
        llong mid = low + (high - low + 1) / 2;
        if (arr[mid] > value)
            high = mid - 1;           
        else
            low = mid;
            
    }
    if (arr[high] <= value)
        return high;
    return -1;
}

llong Solution::countFairPairs(vector<int>& nums, int lower, int upper) {
    std::sort(nums.begin(), nums.end());
    llong ans = 0;
    llong lo = 0;
    llong hi = nums.size() - 1;
    for (llong i = 0; i < nums.size(); ++i) {
        lo = i + 1;
        hi = getUpper(nums, upper - nums[i], lo, hi);
        if (lo > hi)
            return ans;
        lo = getLower(nums, lower - nums[i], i+1, hi);
        if (lo > hi)
            continue;
        ans += hi - lo + 1;
    }
    return ans;
}

class Solution {
    func countFairPairs(_ nums: [Int], _ lower: Int, _ upper: Int) -> Int {
        let nums = nums.sorted()
        var result = 0
        for (index, num) in nums.enumerated() {
            //if num > upper { break }
            // lower
            var posL = -1
            do {
                var left = index+1
                var right = nums.count - 1
                while left <= right {
                    let mid = (left + right) / 2
                    let sum = num + nums[mid]
                    if sum < lower {
                        left = mid + 1
                    } else if sum >= lower {
                        posL = mid
                        right = mid - 1
                    }
                }
            }
            // upper
            var posR = -1
            do {
                var left = index+1
                var right = nums.count - 1
                while left <= right {
                    let mid = (left + right) / 2
                    let sum = num + nums[mid]
                    if sum <= upper {
                        posR = mid
                        left = mid + 1
                    } else {
                        right = mid - 1
                    }
                }
            }
            if posL != -1 && posR != -1 {
                result += posR - posL + 1
            }
        }
        return result
    }
}

func countFairPairs(nums []int, lower int, upper int) int64 {
    n := len(nums)
    if n < 2 {
        return 0
    }

    sort.Ints(nums)
    var count int64

    for i := 0; i < n-1; i++ {
        left := searchLeft(nums, i+1, n-1, lower-nums[i])
        right := searchRight(nums, i+1, n-1, upper-nums[i])

        if left <= right {
            count += int64(right - left + 1)
        }
    }

    return count
}

func searchLeft(nums []int, left, right, target int) int {
    result := right + 1
    for left <= right {
        mid := left + (right-left)/2
        if nums[mid] >= target {
            result = mid
            right = mid - 1
        } else {
            left = mid + 1
        }
    }
    return result
}

func searchRight(nums []int, left, right, target int) int {
    result := left - 1
    for left <= right {
        mid := left + (right-left)/2
        if nums[mid] <= target {
            result = mid
            left = mid + 1
        } else {
            right = mid - 1
        }
    }
    return result
}