给定一个整数数组和一个正整数k，计算差等于k的所有不同对。
null
例如：
Input: arr[] = {1, 5, 3, 4, 2}, k = 3Output: 2There are 2 pairs with difference 3, the pairs are {1, 4} and {5, 2} Input: arr[] = {8, 12, 16, 4, 0, 20}, k = 4Output: 5There are 5 pairs with difference 4, the pairs are {0, 4}, {4, 8}, {8, 12}, {12, 16} and {16, 20}
方法1（简单） 一个简单的解决方案是一对一地考虑所有的对，并检查每一对之间的差异。下面的程序实现了这个简单的解决方案。我们运行两个循环：外部循环选择对中的第一个元素，内部循环寻找另一个元素。如果数组中存在重复项，则此解决方案不起作用，因为要求只计算不同的对。
C++
/* A simple program to count pairs with difference k*/ #include<iostream> using namespace std; int countPairsWithDiffK( int arr[], int n, int k) { int count = 0; // Pick all elements one by one for ( int i = 0; i < n; i++) { // See if there is a pair of this picked element for ( int j = i+1; j < n; j++) if (arr[i] - arr[j] == k || arr[j] - arr[i] == k ) count++; } return count; } // Driver program to test above function int main() { int arr[] = {1, 5, 3, 4, 2}; int n = sizeof (arr)/ sizeof (arr[0]); int k = 3; cout << "Count of pairs with given diff is " << countPairsWithDiffK(arr, n, k); return 0; } |
JAVA
// A simple Java program to //count pairs with difference k import java.util.*; import java.io.*; class GFG { static int countPairsWithDiffK( int arr[], int n, int k) { int count = 0 ; // Pick all elements one by one for ( int i = 0 ; i < n; i++) { // See if there is a pair // of this picked element for ( int j = i + 1 ; j < n; j++) if (arr[i] - arr[j] == k || arr[j] - arr[i] == k) count++; } return count; } // Driver code public static void main(String args[]) { int arr[] = { 1 , 5 , 3 , 4 , 2 }; int n = arr.length; int k = 3 ; System.out.println( "Count of pairs with given diff is " + countPairsWithDiffK(arr, n, k)); } } // This code is contributed // by Sahil_Bansall |
Python3
# A simple program to count pairs with difference k def countPairsWithDiffK(arr, n, k): count = 0 # Pick all elements one by one for i in range ( 0 , n): # See if there is a pair of this picked element for j in range (i + 1 , n) : if arr[i] - arr[j] = = k or arr[j] - arr[i] = = k: count + = 1 return count # Driver program arr = [ 1 , 5 , 3 , 4 , 2 ] n = len (arr) k = 3 print ( "Count of pairs with given diff is " , countPairsWithDiffK(arr, n, k)) |
C#
// A simple C# program to count pairs with // difference k using System; class GFG { static int countPairsWithDiffK( int []arr, int n, int k) { int count = 0; // Pick all elements one by one for ( int i = 0; i < n; i++) { // See if there is a pair // of this picked element for ( int j = i + 1; j < n; j++) if (arr[i] - arr[j] == k || arr[j] - arr[i] == k) count++; } return count; } // Driver code public static void Main() { int []arr = { 1, 5, 3, 4, 2 }; int n = arr.Length; int k = 3; Console.WriteLine( "Count of pairs with " + " given diff is " + countPairsWithDiffK(arr, n, k)); } } // This code is contributed by Sam007. |
PHP
<?php // A simple PHP program to count // pairs with difference k function countPairsWithDiffK( $arr , $n , $k ) { $count = 0; // Pick all elements one by one for ( $i = 0; $i < $n ; $i ++) { // See if there is a pair of // this picked element for ( $j = $i + 1; $j < $n ; $j ++) if ( $arr [ $i ] - $arr [ $j ] == $k or $arr [ $j ] - $arr [ $i ] == $k ) $count ++; } return $count ; } // Driver Code $arr = array (1, 5, 3, 4, 2); $n = count ( $arr ); $k = 3; echo "Count of pairs with given diff is " , countPairsWithDiffK( $arr , $n , $k ); // This code is contributed by anuj_67. ?> |
Javascript
<script> /* A simple program to count pairs with difference k*/ function countPairsWithDiffK(arr, n, k) { count = 0; // Pick all elements one by one for (let i = 0; i < n; i++) { // See if there is a pair of this // picked element for (let j = i+1; j < n; j++) if (arr[i] - arr[j] == k || arr[j] - arr[i] == k ) count++; } return count; } // Driver program to test above function arr = new Array(1, 5, 3, 4, 2); n = arr.length; k = 3; document.write( "Count of pairs with given diff is " + countPairsWithDiffK(arr, n, k)); // This code is contributed by simranarora5sos </script> |
输出：
Count of pairs with given diff is 2
O（n）的时间复杂度 2. )
方法2（使用排序） 我们可以使用O（nLogn）排序算法，如 合并排序 , 堆排序 以下是详细的步骤。
1) Initialize count as 02) Sort all numbers in increasing order.3) Remove duplicates from array.4) Do following for each element arr[i] a) Binary Search for arr[i] + k in subarray from i+1 to n-1. b) If arr[i] + k found, increment count. 5) Return count.
C++
/* A sorting based program to count pairs with difference k*/ #include <iostream> #include <algorithm> using namespace std; /* Standard binary search function */ int binarySearch( int arr[], int low, int high, int x) { if (high >= low) { int mid = low + (high - low)/2; if (x == arr[mid]) return mid; if (x > arr[mid]) return binarySearch(arr, (mid + 1), high, x); else return binarySearch(arr, low, (mid -1), x); } return -1; } /* Returns count of pairs with difference k in arr[] of size n. */ int countPairsWithDiffK( int arr[], int n, int k) { int count = 0, i; sort(arr, arr+n); // Sort array elements /* code to remove duplicates from arr[] */ // Pick a first element point for (i = 0; i < n-1; i++) if (binarySearch(arr, i+1, n-1, arr[i] + k) != -1) count++; return count; } // Driver program int main() { int arr[] = {1, 5, 3, 4, 2}; int n = sizeof (arr)/ sizeof (arr[0]); int k = 3; cout << "Count of pairs with given diff is " << countPairsWithDiffK(arr, n, k); return 0; } |
JAVA
// A sorting base java program to // count pairs with difference k import java.util.*; import java.io.*; class GFG { // Standard binary search function // static int binarySearch( int arr[], int low, int high, int x) { if (high >= low) { int mid = low + (high - low) / 2 ; if (x == arr[mid]) return mid; if (x > arr[mid]) return binarySearch(arr, (mid + 1 ), high, x); else return binarySearch(arr, low, (mid - 1 ), x); } return - 1 ; } // Returns count of pairs with // difference k in arr[] of size n. static int countPairsWithDiffK( int arr[], int n, int k) { int count = 0 , i; // Sort array elements Arrays.sort(arr); // code to remove duplicates from arr[] // Pick a first element point for (i = 0 ; i < n - 1 ; i++) if (binarySearch(arr, i + 1 , n - 1 , arr[i] + k) != - 1 ) count++; return count; } // Driver code public static void main(String args[]) { int arr[] = { 1 , 5 , 3 , 4 , 2 }; int n = arr.length; int k = 3 ; System.out.println( "Count of pairs with given diff is " + countPairsWithDiffK(arr, n, k)); } } // This code is contributed by Sahil_Bansall |
python
# A sorting based program to # count pairs with difference k # Standard binary search function def binarySearch(arr, low, high, x): if (high > = low): mid = low + (high - low) / / 2 if x = = arr[mid]: return (mid) elif (x > arr[mid]): return binarySearch(arr, (mid + 1 ), high, x) else : return binarySearch(arr, low, (mid - 1 ), x) return - 1 # Returns count of pairs with # difference k in arr[] of size n. def countPairsWithDiffK(arr, n, k): count = 0 arr.sort() # Sort array elements # code to remove # duplicates from arr[] # Pick a first element point for i in range ( 0 , n - 2 ): if (binarySearch(arr, i + 1 , n - 1 , arr[i] + k) ! = - 1 ): count + = 1 return count # Driver Code arr = [ 1 , 5 , 3 , 4 , 2 ] n = len (arr) k = 3 print ( "Count of pairs with given diff is " , countPairsWithDiffK(arr, n, k)) # This code is contributed # by Shivi_Aggarwal |
C#
// A sorting base C# program to // count pairs with difference k using System; class GFG { // Standard binary search function static int binarySearch( int []arr, int low, int high, int x) { if (high >= low) { int mid = low + (high - low) / 2; if (x == arr[mid]) return mid; if (x > arr[mid]) return binarySearch(arr, (mid + 1), high, x); else return binarySearch(arr, low, (mid - 1), x); } return -1; } // Returns count of pairs with // difference k in arr[] of size n. static int countPairsWithDiffK( int []arr, int n, int k) { int count = 0, i; // Sort array elements Array.Sort(arr); // code to remove duplicates from arr[] // Pick a first element point for (i = 0; i < n - 1; i++) if (binarySearch(arr, i + 1, n - 1, arr[i] + k) != -1) count++; return count; } // Driver code public static void Main() { int []arr = { 1, 5, 3, 4, 2 }; int n = arr.Length; int k = 3; Console.WriteLine( "Count of pairs with" + " given diff is " + countPairsWithDiffK(arr, n, k)); } } // This code is contributed by Sam007. |
PHP
<?php // A sorting based PHP program to // count pairs with difference k // Standard binary search function function binarySearch( $arr , $low , $high , $x ) { if ( $high >= $low ) { $mid = $low + ( $high - $low )/2; if ( $x == $arr [ $mid ]) return $mid ; if ( $x > $arr [ $mid ]) return binarySearch( $arr , ( $mid + 1), $high , $x ); else return binarySearch( $arr , $low , ( $mid -1), $x ); } return -1; } /* Returns count of pairs with difference k in arr[] of size n. */ function countPairsWithDiffK( $arr , $n , $k ) { $count = 0; $i ; // Sort array elements sort( $arr ); // Code to remove duplicates // from arr[] // Pick a first element point for ( $i = 0; $i < $n - 1; $i ++) if (binarySearch( $arr , $i + 1, $n - 1, $arr [ $i ] + $k ) != -1) $count ++; return $count ; } // Driver Code $arr = array (1, 5, 3, 4, 2); $n = count ( $arr ); $k = 3; echo "Count of pairs with given diff is " , countPairsWithDiffK( $arr , $n , $k ); // This code is contributed by anuj-67. ?> |
Javascript
<script> /* A sorting based program to count pairs with difference k*/ /* Standard binary search function */ function binarySearch(arr, low, high, x) { if (high >= low) { let mid = low + Math.floor((high - low)/2); if (x == arr[mid]) return mid; if (x > arr[mid]) return binarySearch(arr, (mid + 1), high, x); else return binarySearch(arr, low, (mid -1), x); } return -1; } /* Returns count of pairs with difference k in arr[] of size n. */ function countPairsWithDiffK(arr, n, k) { let count = 0, i; // Sort array elements arr.sort((a, b) => a - b); /* code to remove duplicates from arr[] */ // Pick a first element point for (i = 0; i < n-1; i++) if (binarySearch(arr, i+1, n-1, arr[i] + k) != -1) count++; return count; } // Driver program let arr = [1, 5, 3, 4, 2]; let n = arr.length; let k = 3; document.write( "Count of pairs with given diff is " + countPairsWithDiffK(arr, n, k)); // This code is contributed by Surbhi Tyagi. </script> |
输出：
Count of pairs with given diff is 2
时间复杂度：第一步（排序）需要O（nLogn）时间。第二步执行n次二进制搜索，因此第二步的时间复杂度也是O（nLogn）。因此，总体时间复杂度为O（nLogn）。第二步可以优化为O（n），参见 这 .
方法3（使用自平衡BST） 我们也可以像BST一样进行自我平衡 平衡二叉树 或者红黑树来解决这个问题。下面是一个详细的算法。
1) Initialize count as 0.2) Insert all elements of arr[] in an AVL tree. While inserting, ignore an element if already present in AVL tree.3) Do following for each element arr[i]. a) Search for arr[i] + k in AVL tree, if found then increment count. b) Search for arr[i] - k in AVL tree, if found then increment count. c) Remove arr[i] from AVL tree.
上述解决方案的时间复杂度也是O（nLogn），因为对于自平衡二叉搜索树，搜索和删除操作需要O（Logn）时间。
方法4（使用哈希） 对于许多情况，我们还可以使用哈希来实现O（n）的平均时间复杂度。
1) Initialize count as 0.2) Insert all distinct elements of arr[] in a hash map. While inserting, ignore an element if already present in the hash map.3) Do following for each element arr[i]. a) Look for arr[i] + k in the hash map, if found then increment count. b) Look for arr[i] - k in the hash map, if found then increment count. c) Remove arr[i] from hash table.
一个非常简单的情况是，散列在O（n）时间内工作，即值的范围非常小。例如，在以下实现中，数字的范围假定为0到99999。可以使用一种简单的哈希技术将值用作索引。
C++
/* An efficient program to count pairs with difference k when the range numbers is small */ #define MAX 100000 int countPairsWithDiffK( int arr[], int n, int k) { int count = 0; // Initialize count // Initialize empty hashmap. bool hashmap[MAX] = { false }; // Insert array elements to hashmap for ( int i = 0; i < n; i++) hashmap[arr[i]] = true ; for ( int i = 0; i < n; i++) { int x = arr[i]; if (x - k >= 0 && hashmap[x - k]) count++; if (x + k < MAX && hashmap[x + k]) count++; hashmap[x] = false ; } return count; } |
JAVA
/* An efficient program to count pairs with difference k when the range numbers is small */ static int MAX= 100000 ; public static int countPairsWithDiffK( int arr[], int n, int k) { int count = 0 ; // Initialize count // Initialize empty hashmap. boolean hashmap[MAX] = { false }; // Insert array elements to hashmap for ( int i = 0 ; i < n; i++) hashmap[arr[i]] = true ; for ( int i = 0 ; i < n; i++) { int x = arr[i]; if (x - k >= 0 && hashmap[x - k]) count++; if (x + k < MAX && hashmap[x + k]) count++; hashmap[x] = false ; } return count; } // This code is contributed by RohitOberoi. |
Python3
''' An efficient program to count pairs with difference k when the range numbers is small ''' MAX = 100000 ; def countPairsWithDiffK(arr, n, k): count = 0 ; # Initialize count # Initialize empty hashmap. hashmap = [ False for i in range ( MAX )]; # Insert array elements to hashmap for i in range (n): hashmap[arr[i]] = True ; for i in range (n): x = arr[i]; if (x - k > = 0 and hashmap[x - k]): count + = 1 ; if (x + k < MAX and hashmap[x + k]): count + = 1 ; hashmap[x] = False ; return count; # This code is contributed by 29AjayKumar |
C#
/* An efficient program to count pairs with difference k when the range numbers is small */ static int MAX=100000; public static int countPairsWithDiffK( int []arr, int n, int k) { int count = 0; // Initialize count // Initialize empty hashmap. bool hashmap[MAX] = { false }; // Insert array elements to hashmap for ( int i = 0; i < n; i++) hashmap[arr[i]] = true ; for ( int i = 0; i < n; i++) { int x = arr[i]; if (x - k >= 0 && hashmap[x - k]) count++; if (x + k < MAX && hashmap[x + k]) count++; hashmap[x] = false ; } return count; } // This code is contributed by famously. |
Javascript
<script> /* An efficient program to count pairs with difference k when the range numbers is small */ var MAX = 100000; function countPairsWithDiffK(arr, n, k) { var count = 0; // Initialize count // Initialize empty hashmap. var hashmap = Array(MAX).fill( false ); // Insert array elements to hashmap for ( var i = 0; i < n; i++) hashmap[arr[i]] = true ; for ( var i = 0; i < n; i++) { var x = arr[i]; if (x - k >= 0 && hashmap[x - k]) count++; if (x + k < MAX && hashmap[x + k]) count++; hashmap[x] = false ; } return count; } </script> |
方法5（使用排序）
- 对数组进行arr排序
- 取两个指针l和r，都指向第一个元素
- 取差arr[r]–arr[l]
- 如果值diff为K，则递增计数并将两个指针移动到下一个元素
- 如果值差异>k，则将l移动到下一个元素
- 如果值diff
- 返回计数
C++
/* A sorting based program to count pairs with difference k*/ #include <iostream> #include <algorithm> using namespace std; /* Returns count of pairs with difference k in arr[] of size n. */ int countPairsWithDiffK( int arr[], int n, int k) { int count = 0; sort(arr, arr+n); // Sort array elements int l = 0; int r = 0; while (r < n) { if (arr[r] - arr[l] == k) { count++; l++; r++; } else if (arr[r] - arr[l] > k) l++; else // arr[r] - arr[l] < sum r++; } return count; } // Driver program to test above function int main() { int arr[] = {1, 5, 3, 4, 2}; int n = sizeof (arr)/ sizeof (arr[0]); int k = 3; cout << "Count of pairs with given diff is " << countPairsWithDiffK(arr, n, k); return 0; } |
JAVA
// A sorting based Java program to // count pairs with difference k import java.util.*; class GFG { /* Returns count of pairs with difference k in arr[] of size n. */ static int countPairsWithDiffK( int arr[], int n, int k) { int count = 0 ; Arrays.sort(arr); // Sort array elements int l = 0 ; int r = 0 ; while (r < n) { if (arr[r] - arr[l] == k) { count++; l++; r++; } else if (arr[r] - arr[l] > k) l++; else // arr[r] - arr[l] < sum r++; } return count; } // Driver program to test above function public static void main(String[] args) { int arr[] = { 1 , 5 , 3 , 4 , 2 }; int n = arr.length; int k = 3 ; System.out.println( "Count of pairs with given diff is " + countPairsWithDiffK(arr, n, k)); } } // This code is contributed by Prerna Saini |
Python3
# A sorting based program to # count pairs with difference k def countPairsWithDiffK(arr,n,k): count = 0 # Sort array elements arr.sort() l = 0 r = 0 while r<n: if arr[r] - arr[l] = = k: count + = 1 l + = 1 r + = 1 # arr[r] - arr[l] < sum elif arr[r] - arr[l]>k: l + = 1 else : r + = 1 return count # Driver code if __name__ = = '__main__' : arr = [ 1 , 5 , 3 , 4 , 2 ] n = len (arr) k = 3 print ( "Count of pairs with given diff is " , countPairsWithDiffK(arr, n, k)) # This code is contributed by # Shrikant13 |
C#
// A sorting based C# program to count // pairs with difference k using System; class GFG { /* Returns count of pairs with difference k in arr[] of size n. */ static int countPairsWithDiffK( int []arr, int n, int k) { int count = 0; // Sort array elements Array.Sort(arr); int l = 0; int r = 0; while (r < n) { if (arr[r] - arr[l] == k) { count++; l++; r++; } else if (arr[r] - arr[l] > k) l++; else // arr[r] - arr[l] < sum r++; } return count; } // Driver program to test above function public static void Main() { int []arr = {1, 5, 3, 4, 2}; int n = arr.Length; int k = 3; Console.Write( "Count of pairs with " + "given diff is " + countPairsWithDiffK(arr, n, k)); } } // This code is contributed by nitin mittal. |
PHP
<?php // A sorting based program to count // pairs with difference k // Returns count of pairs with // difference k in arr[] of size n. function countPairsWithDiffK( $arr , $n , $k ) { $count = 0; // Sort array elements sort( $arr ); $l = 0; $r = 0; while ( $r < $n ) { if ( $arr [ $r ] - $arr [ $l ] == $k ) { $count ++; $l ++; $r ++; } else if ( $arr [ $r ] - $arr [ $l ] > $k ) $l ++; // arr[r] - arr[l] < k else $r ++; } return $count ; } // Driver Code $arr = array (1, 5, 3, 4, 2); $n = count ( $arr ); $k = 3; echo "Count of pairs with given diff is " , countPairsWithDiffK( $arr , $n , $k ); // This code is contributed by anuj_67, ?> |
Javascript
<script> // Javascript program to // count pairs with difference k /* Returns count of pairs with difference k in arr[] of size n. */ function countPairsWithDiffK(arr, n, k) { let count = 0; arr.sort(); // Sort array elements let l = 0; let r = 0; while (r < n) { if (arr[r] - arr[l] == k) { count++; l++; r++; } else if (arr[r] - arr[l] > k) l++; else // arr[r] - arr[l] < sum r++; } return count; } // Driver program let arr = [1, 5, 3, 4, 2]; let n = arr.length; let k = 3; document.write( "Count of pairs with given diff is " + countPairsWithDiffK(arr, n, k)); </script> |
输出：
Count of pairs with given diff is 2
时间复杂度：O（nlogn）
方法6（使用二进制搜索）（适用于数组中的重复项）：
1） 将计数初始化为0。
2） 按递增顺序对所有数字进行排序。
4） 对每个元素arr[i]执行以下操作
a） 二进制搜索子数组arr[i+1，N-1]中第一次出现的arr[i]+k，让这个索引为“X”。
b） 如果未找到arr[i]+k，则返回大于arr[i]+k的值的第一次出现的索引。
c） 重复步骤 A. 和 B 要搜索arr[i]+k+1的首次出现，请将该索引设为“Y”。
d） 用“Y–X”递增计数。
5） 返回计数。
C++
#include <bits/stdc++.h> using namespace std; int BS( int arr[], int X, int low, int N) { int high = N - 1; int ans = N; while (low <= high) { int mid = low + (high - low) / 2; if (arr[mid] >= X) { ans = mid; high = mid - 1; } else low = mid + 1; } return ans; } int countPairsWithDiffK( int arr[], int N, int k) { int count = 0; sort(arr, arr + N); for ( int i = 0; i < N; ++i) { int X = BS(arr, arr[i] + k, i + 1, N); if (X != N) { int Y = BS(arr, arr[i] + k + 1, i + 1, N); count += Y - X; } } return count; } int main() { int arr[] = { 1, 3, 5, 8, 6, 4, 6 }; int n = sizeof (arr) / sizeof (arr[0]); int k = 2; cout << "Count of pairs with given diff is " << countPairsWithDiffK(arr, n, k); return 0; } // This code is contributed by umadevi9616 |
JAVA
import java.io.*; class GFG { static int BS( int [] arr, int X, int low) { int high = arr.length - 1 ; int ans = arr.length; while (low <= high) { int mid = low + (high - low) / 2 ; if (arr[mid] >= X) { ans = mid; high = mid - 1 ; } else low = mid + 1 ; } return ans; } static int countPairsWithDiffK( int [] arr, int N, int k) { int count = 0 ; Arrays.sort(arr); for ( int i = 0 ; i < N ; ++i) { int X = BS(arr, arr[i] + k, i + 1 ); if (X != N) { int Y = BS(arr, arr[i] + k + 1 , i + 1 ); count += Y - X; } } return count; } public static void main (String[] args) { int arr[] = { 1 , 3 , 5 , 8 , 6 , 4 , 6 }; int n = arr.length; int k = 2 ; System.out.println( "Count of pairs with given diff is " + countPairsWithDiffK(arr, n, k)); } } |
Python3
def BS(arr, X, low): high = len (arr) - 1 ; ans = len (arr); while (low < = high): mid = low + (high - low) / / 2 ; if (arr[mid] > = X): ans = mid; high = mid - 1 ; else : low = mid + 1 ; return ans; def countPairsWithDiffK(arr, N, k): count = 0 ; arr.sort(); for i in range (N): X = BS(arr, arr[i] + k, i + 1 ); if (X ! = N): Y = BS(arr, arr[i] + k + 1 , i + 1 ); count + = Y - X; return count; if __name__ = = '__main__' : arr = [ 1 , 3 , 5 , 8 , 6 , 4 , 6 ]; n = len (arr); k = 2 ; print ( "Count of pairs with given diff is " , countPairsWithDiffK(arr, n, k)); # This code is contributed by shikhasingrajput |
C#
using System; class GFG{ static int BS( int [] arr, int X, int low) { int high = arr.Length - 1; int ans = arr.Length; while (low <= high) { int mid = low + (high - low) / 2; if (arr[mid] >= X) { ans = mid; high = mid - 1; } else low = mid + 1; } return ans; } static int countPairsWithDiffK( int [] arr, int N, int k) { int count = 0; Array.Sort(arr); for ( int i = 0 ; i < N ; ++i) { int X = BS(arr, arr[i] + k, i + 1); if (X != N) { int Y = BS(arr, arr[i] + k + 1, i + 1); count += Y - X; } } return count; } // Driver code public static void Main( string [] args) { int []arr = { 1, 3, 5, 8, 6, 4, 6 }; int n = arr.Length; int k = 2; Console.WriteLine( "Count of pairs with given diff is " + countPairsWithDiffK(arr, n, k)); } } // This code is contributed by ukasp |
Javascript
<script> function BS(arr, X, low) { let high = arr.length - 1; let ans = arr.length; while (low <= high) { let mid = low + (high - low) / 2; if (arr[mid] >= X) { ans = mid; high = mid - 1; } else low = mid + 1; } return ans; } function countPairsWithDiffK(arr, N, k) { let count = 2; arr.sort(); for (let i = 0 ; i < N ; ++i) { let X = BS(arr, arr[i] + k, i + 1); if (X != N) { let Y = BS(arr, arr[i] + k + 1, i + 1); count += Y - X; } } return count; } // Driver code let arr = [ 1, 3, 5, 8, 6, 4, 6 ]; let n = arr.length; let k = 3; document.write( "Count of pairs with given diff is " + countPairsWithDiffK(arr, n, k)); // This code is contributed by shivanisinghss2110 </script> |
时间复杂度：O（N*log（N））
如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请写评论
© 版权声明
文章版权归作者所有，未经允许请勿转载。
THE END
![关于”PostgreSQL错误：关系[表]不存在“问题的原因和解决方案-yiteyi-C++库](https://www.yiteyi.com/wp-content/themes/zibll/img/thumbnail.svg)
