Space-time tradeoff

Brute force will solve this problem, but leetcode will reject because of time limit.

Two Sum + Two Sum = 4 Sum

  • build two number's sum cache { 42 : [index1, index2], ... }
  • foreach key in cache and sum - key in cache, add the cartesian product of the values to the result collection