给定一个排序的整数数组和数字x，任务是对数组中的和小于x的对进行计数。 例如：
null
Input : arr[] = {1, 3, 7, 9, 10, 11} x = 7Output : 1There is only one pair (1, 3)Input : arr[] = {1, 2, 3, 4, 5, 6, 7, 8} x = 7Output : 6Pairs are (1, 2), (1, 3), (1, 4), (1, 5) (2, 3) and (2, 4)
A. 简单解决方案 对于这个问题，运行两个循环，逐个生成所有对，并检查当前对的和是否小于x。 一 有效解决方案 这个问题的关键是取l和r变量中索引的初始值和最后一个值。
1) Initialize two variables l and r to find the candidate elements in the sorted array. (a) l = 0 (b) r = n - 12) Initialize : result = 02) Loop while l < r. // If current left and current // right have sum smaller than x, // the all elements from l+1 to r // form a pair with current (a) If (arr[l] + arr[r] < x) result = result + (r - l) (b) Else r--; 3) Return result
以下是上述步骤的实施情况。
C++
// C++ program to count pairs in an array // whose sum is less than given number x #include<bits/stdc++.h> using namespace std; // Function to count pairs in array // with sum less than x. int findPairs( int arr[], int n, int x) { int l = 0, r = n-1; int result = 0; while (l < r) { // If current left and current // right have sum smaller than x, // the all elements from l+1 to r // form a pair with current l. if (arr[l] + arr[r] < x) { result += (r - l); l++; } // Move to smaller value else r--; } return result; } // Driven code int main() { int arr[] = {1, 2, 3, 4, 5, 6, 7, 8}; int n = sizeof (arr)/ sizeof ( int ); int x = 7; cout << findPairs(arr, n, x); return 0; } |
JAVA
// Java program to count pairs in an array // whose sum is less than given number x class GFG { // Function to count pairs in array // with sum less than x. static int findPairs( int arr[], int n, int x) { int l = 0 , r = n - 1 ; int result = 0 ; while (l < r) { // If current left and current // right have sum smaller than x, // the all elements from l+1 to r // form a pair with current l. if (arr[l] + arr[r] < x) { result += (r - l); l++; } // Move to smaller value else r--; } return result; } // Driver method public static void main(String[] args) { int arr[] = { 1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 }; int n = arr.length; int x = 7 ; System.out.print(findPairs(arr, n, x)); } } // This code is contributed by Anant Agarwal. |
Python3
# Python3 program to count pairs # in an array whose sum is less # than given number x # Function to count pairs in array # with sum less than x. def findPairs(arr, n, x): l = 0 ; r = n - 1 result = 0 while (l < r): # If current left and current # right have sum smaller than x, # the all elements from l+1 to r # form a pair with current l. if (arr[l] + arr[r] < x): result + = (r - l) l + = 1 # Move to smaller value else : r - = 1 return result # Driver Code arr = [ 1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 ] n = len (arr) x = 7 print (findPairs(arr, n, x)) # This code is contributed by Anant Agarwal. |
C#
// C# program to count pairs in // an array whose sum is less // than given number x using System; class GFG { // Function to count pairs in array // with sum less than x. static int findPairs( int []arr, int n, int x) { int l = 0, r = n - 1; int result = 0; while (l < r) { // If current left and current // right have sum smaller than x, // the all elements from l+1 to r // form a pair with current l. if (arr[l] + arr[r] < x) { result += (r - l); l++; } // Move to smaller value else r--; } return result; } // Driver code public static void Main(String[] args) { int []arr = {1, 2, 3, 4, 5, 6, 7, 8}; int n = arr.Length; int x = 7; Console.Write(findPairs(arr, n, x)); } } // This code is contributed by parashar... |
PHP
<?php // PHP program to count pairs in an array // whose sum is less than given number x // Function to count pairs in array // with sum less than x. function findPairs( $arr , $n , $x ) { $l = 0; $r = $n - 1; $result = 0; while ( $l < $r ) { // If current left and current // right have sum smaller than x, // the all elements from l+1 to r // form a pair with current l. if ( $arr [ $l ] + $arr [ $r ] < $x ) { $result += ( $r - $l ); $l ++; } // Move to smaller value else $r --; } return $result ; } // Driver Code $arr = array (1, 2, 3, 4, 5, 6, 7, 8); $n = sizeof( $arr ) / sizeof( $arr [0]); $x = 7; echo findPairs( $arr , $n , $x ); return 0; // This code is contributed by nitin mittal. ?> |
Javascript
<script> //javascript program to count pairs in an array // whose sum is less than given number x // Function to count pairs in array // with sum less than x. function findPairs(arr,n,x) { let l = 0, r = n-1; let result = 0; while (l < r) { // If current left and current // right have sum smaller than x, // the all elements from l+1 to r // form a pair with current l. if (arr[l] + arr[r] < x) { result += (r - l); l++; } // Move to smaller value else r--; } return result; } let arr = [1, 2, 3, 4, 5, 6, 7, 8]; let n = arr.length; let x = 7; document.write(findPairs(arr,n,x)); // This code is contributed by vaibhavrabadiya117. </script> |
输出
6
时间复杂度：O（n） 空间复杂性：O（1）
使用基于策略的数据结构：
它也适用于未排序的数组
C++
#include <iostream> using namespace std; #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> using namespace __gnu_pbds; #define ordered_set tree<pair< int , int >, null_type, less<pair< int , int > >, rb_tree_tag, tree_order_statistics_node_update> int countPair(vector< int > v, int sum) { int ans = 0; ordered_set st; int y = 0; for ( auto i = v.rbegin(); i != v.rend(); i++) { int num = *i; if (st.empty()) st.insert({ num, y }); else { int left = sum - num; ans += st.order_of_key({ left, -1 }); st.insert({ num, y }); } y++; } return ans; } int main() { int n; cin >> n; vector< int > v{ 1, 2, 3, 4, 5, 6, 7, 8 }; int sum = 7; cout << countPair(v, sum); return 0; } |
输出
6
分机： 如果数组是未排序的，那么我们可以先对数组进行排序，然后应用上述方法在O（n logn）时间内求解。 相关文章： 计算差等于k的所有不同对 用给定的和数对 参考： https://www.quora.com/Given-a-sorted-integer-array-and-number-z-count-all-pairs-x-y-in-the-array-so-that-x-+-y-z-Can-it-be-done-in-O-n 本文由 丹麦拉扎 .如果你喜欢GeekSforgek，并想贡献自己的力量，你也可以使用 写极客。组织 或者把你的文章寄到contribute@geeksforgeeks.org.看到你的文章出现在Geeksforgeks主页上，并帮助其他极客。 如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请写下评论。
© 版权声明
文章版权归作者所有，未经允许请勿转载。
THE END
![关于”PostgreSQL错误：关系[表]不存在“问题的原因和解决方案-yiteyi-C++库](https://www.yiteyi.com/wp-content/themes/zibll/img/thumbnail.svg)
