Dovendo in ogni caso scorrere completamente due array di N ed M elementi credo sia impossibile individuare un algoritmo con complessità inferiore a O(N x M)
Andrebbero piuttosto riviste le strutture dati.