Rashi (on Devarim 25:17) comments that Amalek represents "mikreh" - coincidence. That is, Amalek personifies denial of Hashem's existence and interaction with the universe, positing that all which occurs is due to coincidence and happenstance, rather than due to God's will and planning.
As I explained in greater detail in the dvar Torah about drinking on Purim, a major theme of Purim is the recognition that God controls all - even though we cannot perceive His hand in the course of events as they unfold. That which seems to be natural coincidence is really Hashem's hashgacha - providence - and Purim demonstrates how this hashgacha works in a world without open miracles, which are reserved only for periods in which the Beis Ha-Mikdash stands and God's glory is dramatically manifest. Thus, although things would seem to be quite natural in the present state, Hashem operates from behind the scenes in the mode of "Hester Panim" ["Hidden Visage"], still fully controlling all according to His master plan, with His hand "pulling the strings" of life, despite our inability to see it directly.
Whereas Amalek argues that the course of life and history are arbitrary (for we cannot often directly perceive Hashem's involvement, as in the days of Mordechai and Esther as well as today), Purim enthusiastically counters that all is part of Hashem's perfectly-planned scheme and it affirms His continued interaction from behind the scenes. This is the connection between Parshas Zachor and Purim.