“This is the 20th day of my participation in the First Challenge 2022. For details: First Challenge 2022.”

Day 42 2021.02.09

2006. Number of pairs whose absolute difference is K

  • Leetcode: leetcode-cn.com/problems/co…
  • Difficulty: Easy
  • Method: hash table

The main idea

  • Ideological change, some of the positive is not very easy to do the topic, you can try upside down.
  • Based on its position, ➕k, determine how many of these numbers are in front of it.

The title

  • 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.

The sample

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

prompt

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

solution

Violent solution

  • Use a two-layer loop, one layer traversali, one layer traversalj, determine whether the absolute value of the difference between two adjacent numbers in the array is K, and count all the number pairs that meet the conditions.
var countKDifference = function(nums, k) {
  let ans = 0;
  for(let i = 0; i < nums.length; i++) {
    for(let j = i + 1; j < nums.length; j++) {
      if(Math.abs(nums[i] - nums[j]) == k) ans++; }}return ans;
};
Copy the code

Hash table + one traversal (single layer)

  • | nums[I] -nums [j] | = kCan be converted tonums[i] = nums[j] + kornums[i] = nums[j] - k
  • In this way, the problem is converted to: in the current position, find the previous number of such numbers based on the current value plus k, so in the traversal process, usemapSet records the number of occurrences that passo(1)To get the data you want.
var countKDifference = function(nums, k) {
  // Hash table solution
  let map = new Map(a);let num = 0;
  for(let i = 0; i < nums.length; i++) {
    // j + k = i || j - k = i
    num += (map.get(nums[i] + k) || 0) + (map.get(nums[i] - k) || 0);
    // console.log('num',nums[i] + k);
    map.set(nums[i], map.get(nums[i]) + 1 || 1);
    // console.log('map',map);
  }
  return num;
};
Copy the code