Element in Linked List finden und vergleichen

[Sleepover (Gast)]

Guten morgen, ich beschäftige im Moment zum ersten mal mit einer 
Programmiersprache und habe ein Problem, was ich zwar lösen kann, aber 
mit einer miserablen Laufzeit.

Problem:

Es ist gegeben ein Array  array ={1,2,3} und eine  LinkedList<int[]> die 
wie folgt ausschaut linkedList={{1,2,2},{1,3,2},{3,2,1}}.
Geprüft werden soll, dass jede Untermenge in linkedList (nennt man dies 
Untermenge?) ein oder mehrere, aber nur Elemente aus dem Array hat.
Wenn in einen der Untermengen eine 7 vorkommt und diese ist nicht im 
array={1,2,3}, sollte es erkannt werden.


Meine brute force Lösung waren 3 Forscheleifen, wobei ich jede 
Untermenge in der ersten in einen Array packe und in den nächsten zwei 
Forschleifen die einzelnen Elemente der arrays vergleiche => Laufzeit 
O(n^3), also unschöne Nummer.

Leider fehlt mir etwas der Rüststoff, wie ich dieses Problem ganz 
einfach löse und es wäre nett, wenn mir hier Jemand helfen könnte.

[DPA (Gast)]

Eine Methode wäre statt dem Array ein Hash map zu programmieren. Du hast 
dort quasi ein Array von Arrays. Fürs erste Array nutzt du den gesuchten 
Wert (oder den Hashwert eines Objekts), bzw. einen Teil davon, als 
Index. Im ausgewählten Array suchst du dann normal danach. Im Idealfall 
gibt es nur 1-2 Einträge pro Array, womit dass dann sehr schnell geht. 
Jenachdem bekommt man dann praktisch O(1).

Oder kannst du die Elemente der Listen und Arrays sortiert halten?
Dann könntest du eine Schleife mit 2 Laufwariablen machen. Wenn a<b, 
nächstes a. Wenn b<a, nicht gefunden. Wenn a==b, nächstes b.

Natürlich gibt es noch viele andere Strukturen und Algorithmen, die man 
nehmen könnte. Die sind mir halt spontan so eingefallen.