要素ごとにリストを走査し直す解法では、処理量がO(n^2)になります。ハッシュを使う構造なら内側の走査がなくなります:集合は「この値を前に見たか?」に平均で定数時間で答え、マップは「何回?」や「どこに?」に答えます。
ループを書く前に、保存する状態が何を意味するかを言葉にしてください。ペアを数える場合、マップには現在の要素より前の要素だけを入れるので、先に検索し、後で保存してください。その順序を間違えると、要素が自分自身とペアになってしまいます。
マップのキーには、計算して作った値も使えます。単語の文字を並べ替えると、文字の順序を入れ替えたものはすべて同じキーになるので、1回の走査でグループ化できます。
代償はメモリです:保存する分として追加の空間がO(n)かかります。ハッシュを使った解法が失敗しやすいケースをテストしてください:空のリスト、要素が1つ、重複、負の数、そしてJavaではintに収まらない合計です。