• Small knowledge, big challenge! This article is participating in the creation activity of “Essential Tips for Programmers”.

Thank you very much for reading this article. Welcome [👍 like] [⭐ collect] [📝 comment] ~ Give up is not difficult, But insists it must be very cool ~ hope we all can be a little bit of progress every day ~ in this paper, from two headed white hat original ~ https://juejin.cn/user/2771185768884824/posts blog

Number of pairs of numbers whose absolute difference is K:

Give you an integer array nums and an integer k, would you please return number for the number of (I, j), meet I < j and | nums [I] – nums [j] | = = k.

| | x value is defined as:

  • If x >= 0, then the value is x.
  • If x is less than 0, then the value is minus x.

Sample 1

Input: nums = [1,2,2,1], k = 1 Output: 4Copy the code

,2,2,1,2,2,1 [1] [1] [1,2,2,1],2,2,1 [1]

The sample 2

Input: nums = [1,3], k = 3 output: 0 explanation: no absolute value of any pair difference is 3.Copy the code

Sample 3

Input: nums = [3,2,1,5,4], k = 2 Output: 3Copy the code

,2,1,5,4,2,1,5,4 [3] [3],2,1,5,4 [3]

prompt

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

Analysis of the

  • I could have just done it, double loop, order n^2^ time.
  • But to do an algorithm, you need to find a faster way. The answer just counts, which means we don’t care about the array index of the answer, so we can think about it in terms of counting. The range of nums[I] is given in the hint, so we can deduce it forward by looking directly at the number of pairs that satisfy the answer, rather than working double-dimensionally to determine whether the current pair satisfies the condition.

Answer key

java

class Solution {
    public int countKDifference(int[] nums, int k) {
        // Count the number from 1 to 100
		int[] counter = new int[101];
		for (int num : nums) {
			counter[num]++;
		}

		int ans = 0;

		// Do not consider counter[i-k] because counter[I + k] has been counted before
		for (int i = 1; i + k < 101; ++i) {
			ans += counter[i] * counter[i + k];
		}

		returnans; }}Copy the code

c

int countKDifference(int* nums, int numsSize, int k){
    // Count the number from 1 to 100
    int counter[101] = {0};
    for (int i = 0; i < numsSize; ++i) {
        ++counter[nums[i]];
    }

    int ans = 0;

    // Do not consider counter[i-k] because counter[I + k] has been counted before
    for (int i = 1; i + k < 101; ++i) {
        ans += counter[i] * counter[i + k];
    }

    return ans;
}
Copy the code

c++

class Solution {
public:
    int countKDifference(vector<int>& nums, int k) {
        // Count the number from 1 to 100
        int counter[101] = {0};
        for (const auto num : nums) {
            ++counter[num];
        }

        int ans = 0;

        // Do not consider counter[i-k] because counter[I + k] has been counted before
        for (int i = 1; i + k < 101; ++i) {
            ans += counter[i] * counter[i + k];
        }

        returnans; }};Copy the code

python

class Solution:
    def countKDifference(self, nums: List[int], k: int) - >int:
        # count the number from 1 to 100
        counter = [0] * 101
        for num in nums:
            counter[num] += 1

        ans = 0

        Do not consider counter[i-k] because counter[I + k] has been counted before
        for i in range(1.101 - k):
            ans += counter[i] * counter[i + k]

        return ans
Copy the code

go

func countKDifference(nums []int, k int) int {
    // Count the number from 1 to 100
    var counter [101]int
	for _, num := range nums {
		counter[num]++
	}

	ans := 0

    // Do not consider counter[i-k] because counter[I + k] has been counted before
	for i := 1; i + k < 101; i++ {
		ans += counter[i] * counter[i + k]
	}

	return ans
}
Copy the code

rust

impl Solution {
    pub fn count_k_difference(nums: Vec<i32>, k: i32) - >i32 {
        // Count the number from 1 to 100
        let mut counter = vec![0;101];
        nums.iter().for_each(|n| { counter[*n as usize] + =1; });

        let mut ans = 0;

        // Do not consider counter[i-k] because counter[I + k] has been counted before
        (1.101 - k).for_each(|i| { ans += counter[i as usize] * counter[(i + k) as usize]; }); ans } }Copy the code

Original topic portal