As far as I know, in situations like this - when you deleted the post yourself, all you have to do is to check the tab with delete votes in your profile. If you do not have too deleted your posts too often, you'll see only a few posts there, so this might be a reasonable way to find the one you're interested in.
This tab contains both self-deletions and votes to delete cast on other users' posts. But the latter is only relevant for 10k+ users - who have easier access to their own deleted stuff anyway - simply by including deleted:1 in the search query. I will also mention that among the delete votes you will also see posts that you have deleted and later undeleted.
A situation would be different for posts deleted by roomba or by other users who can delete posts. (Privilege to cast delete votes on question obtained at 10k reputation points. Starting from 20k reputation points users can also deleted answers and there are less restrictions on deleting questions.) Obviously, in such cases you will not find the post among your own deletion votes.
More information about searching for deleted posts: Can I somewhere see my own deleted questions?
deleted:1
$\endgroup$ – user9072 Feb 12 '16 at 1:48