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;
    }
};