454. 4Sum II

Question Description

Given four lists A, B, C, D of integer values, compute how many tuples (i, j, k, l) there are such that A[i] + B[j] + C[k] + D[l] is zero.
To make problem a bit easier, all A, B, C, D have same length of N where 0 ≤ N ≤ 500. All integers are in the range of -228 to 228 - 1 and the result is guaranteed to be at most 231 - 1.

主要思路

本来是打算暴力破解的，但是超时间了，所以只能不断优化，这是其实就是将ABCD四个向量拆开，然后两两计算和，存到一个map，如果这两次的和（第二次是取得相反数），如果这两次的值是相同的，那么就算作找到一次

C++ code

class Solution {
public:
int fourSumCount(vector<int>& A, vector<int>& B, vector<int>& C, vector<int>& D) {
      int N = A.size();
      int res = 0;
      unordered_map<int, int> m;//声明一个无序表，来存储下面的和
      // n^2
      for (int k = 0; k <N; ++k) {
        for (int p = 0; p <N; ++p) {
        int tmp = C[k] + D[p];
        if (m.count(tmp) > 0)//判断map里面有没有tem这个元素key
 {
            m[tmp] += 1;//有的话将其值设置成2
        } else {
            m[tmp] = 1;//没有的话设置成1
        }
        }
      }
      
      for (int i = 0; i <N; ++i) {
        for (int j = 0; j <N; ++j) {
          int tmp = 0-A[i] - B[j];//另外两个数组相加的和的倒数
          if (m.count(tmp) > 0) {
            res += m[tmp];//如果前面C、D的和与A、B里面的和相等，那么就将想到的和相加
          }
        }
      }
      return res;
    }
};