Skip to content

Latest commit

 

History

History
 
 

2006

Folders and files

NameName
Last commit message
Last commit date

parent directory

..
 
 

Given an integer array nums and an integer k, return the number of pairs (i, j) where i < j such that |nums[i] - nums[j]| == k.

The value of |x| is defined as:

  • x if x >= 0.
  • -x if x < 0.

 

Example 1:

Input: nums = [1,2,2,1], k = 1
Output: 4
Explanation: The pairs with an absolute difference of 1 are:
- [1,2,2,1]
- [1,2,2,1]
- [1,2,2,1]
- [1,2,2,1]

Example 2:

Input: nums = [1,3], k = 3
Output: 0
Explanation: There are no pairs with an absolute difference of 3.

Example 3:

Input: nums = [3,2,1,5,4], k = 2
Output: 3
Explanation: The pairs with an absolute difference of 2 are:
- [3,2,1,5,4]
- [3,2,1,5,4]
- [3,2,1,5,4]

 

Constraints:

  • 1 <= nums.length <= 200
  • 1 <= nums[i] <= 100
  • 1 <= k <= 99

Similar Questions:

Solution 1. Brute Force

// OJ: https://leetcode.com/problems/count-number-of-pairs-with-absolute-difference-k/
// Author: github.com/lzl124631x
// Time: O(N^2)
// Space: O(1)
class Solution {
public:
    int countKDifference(vector<int>& A, int k) {
        int N = A.size(), ans = 0;
        for (int i = 0; i < N; ++i) {
            for (int j = i + 1; j < N; ++j) {
                ans += abs(A[i] - A[j]) == k;
            }
        }
        return ans;
    }
};

Solution 2. Sliding Window

After sorting the array A, we can use sliding window to count the number of elements == A[i] + k so that we just traverse A once.

// OJ: https://leetcode.com/problems/count-number-of-pairs-with-absolute-difference-k/
// Author: github.com/lzl124631x
// Time: O(NlogN)
// Space: O(1)
class Solution {
public:
    int countKDifference(vector<int>& A, int k) {
        int N = A.size(), ans = 0, j = 0;
        sort(begin(A), end(A));
        for (int i = 0; i < N; ) {
            int n = A[i], cnt = 0;
            while (i < N && A[i] == n) ++i, ++cnt;
            while (j < N && A[j] < n + k) ++j;
            int start = j;
            while (j < N && A[j] == n + k) ++j;
            ans += (j - start) * cnt;
        }
        return ans;
    }
};

Solution 3. Frequency Map

// OJ: https://leetcode.com/problems/count-number-of-pairs-with-absolute-difference-k/
// Author: github.com/lzl124631x
// Time: O(N)
// Space: O(C) where `C` is the range of numbers in `A`.
class Solution {
public:
    int countKDifference(vector<int>& A, int k) {
        int N = A.size(), ans = 0, cnt[101] = {};
        for (int n : A) {
            ans += (n + k <= 100 ? cnt[n + k] : 0) + (n - k >= 1 ? cnt[n - k] : 0);
            cnt[n]++;
        }
        return ans;
    }
};