Spiral Matrix

解题思路

  1. 首先，自然是先思考最简单的解法 - 暴搜。

  2. 然后，想如何优化，一开始的思路，是参照 3Sum，先写出 2Sum，再挨个来，其实也就是 sort 后的暴搜，没有实质性的改变。

  3. 于是，为了优化时间，往增加空间上思考，于是得出将其分为两部分，每个部分都遍历得到一个 map，然后搜索 map 即可。

  4. 最后，再次优化的思路是第二部分不再需要先存到 map 中，而是在遍历的过程中搜索前一个 map 即可。

代码

class Solution {
public:
    int fourSumCount(vector<int>& A, vector<int>& B, vector<int>& C, vector<int>& D) {
        unordered_map<int, int> ab;
        for (int a : A) {
            for (int b : B) {
                ab[a + b] += 1;
            }
        }
        int count = 0;
        for (int c : C) {
            for (int d : D) {
                int half = c + d;
                int abCount = ab[-half];
                if (abCount) {
                    count += abCount;
                }
            }
        }
        return count;
    }
};