how to reduce time complexity of nested loop or replace nested loop
Hi experts,
I tried to resolve the issue here, but my solution exceeded 3s for 3 cases. Can you all please suggest?
HERE IS THE PROBLEM:
Given an array a of positive integers, find the number of pairs of integers for which the difference between the two numbers is equal to a given number k. Since the number of pairs could be quite large, take it modulo 109 + 7 for your output.
Example
For k = 3 and a = [1, 6, 8, 2, 4, 9, 12], the output should be
solution(k, a) = 3.
There are three pairs of integers whose difference is equal to 3: (1, 4), (6, 9) and (9, 12).
Input/Output
[execution time limit] 3 seconds (java)
[input] integer k
The specified difference between two numbers.
Guaranteed constraints:
1 ≤ k ≤ 1000.
[input] array.integer a
Guaranteed constraints:
1 ≤ a.length ≤ 105,
1 ≤ a[i] ≤ 1000.
[output] integer
The number of pairs of integers with difference k modulo 109 + 7.
[Java] Syntax Tips
// Prints help message to the console
// Returns a string
//
// Globals declared here will cause a compilation error,
// declare variables inside the function instead!
String helloWorld(String name) {
System.out.println("This prints to the console when you Run Tests");
return "Hello, " + name;
}
===================================
Here's my solution:
int solution(int k, int[] a) {
int number = 0;
for(int i=0; i<a.length; i++)
{
for(int j=i+1; j<a.length; j++)
{
if(Math.abs(a[i]-a[j])==k)
number++;
}
}
return number;
}