For array A
a good pair is defined as a pair where A[i] + A[j] = i + j
where i < j
and i
and j
are the indices of the array.
Example A = [1, 0, 3, 2]
The answer is 4
. The pairs (0,1), (1, 2), (0, 3), (2, 3)
are good pairs.
This was my approach A[i] + A[j] = i + j
so A[i] - i = j - A[j]
and the code was something like this
int answer = 0;
map<int, int> map;
map.insert(A[0], 1)
for(int i = 1; i < A.size(); ++i){
int right = i - A[i];
if(map.find(right) != map.end()){
answer += map[right];
}
int left = A[i] - i;
if(map.find(left) != map.end()){
map[left] += 1;
}
else{
map.insert({left, 1});
}
}
This solution passed only half the test cases. Can someone tell me the corner cases i missed.
Aucun commentaire:
Enregistrer un commentaire