暴力
不用多说，肯定是超时的，时间复杂度达到了O(n^4)
class Solution {
public:
int fourSumCount(vector<int>& nums1, vector<int>& nums2, vector<int>& nums3, vector<int>& nums4) {
int num = 0;
for(int i=0;i<nums1.size();i++){
for(int j=0;j<nums2.size();j++){
for(int k=0;k<nums3.size();k++){
for(int h=0;h<nums4.size();h++){
if(nums1[i]+nums2[j]+nums3[k]+nums4[h]==0){
num++;
}
}
}
}
}
return num;
}
};
优化一：将四重循环减少为三重循环（使用一个map来存储）
哎呀，还是超时
class Solution {
public:
int fourSumCount(vector<int>& nums1, vector<int>& nums2, vector<int>& nums3, vector<int>& nums4) {
int num = 0;
unordered_map<int,int> num1_map;
unordered_map<int,int> num2_map;
unordered_map<int,int> num3_map;
unordered_map<int,int> num4_map;
for(int i=0;i<nums1.size();i++){
//如果这个数在map中
if(num1_map.find(nums1[i])!=num1_map.end()){
num1_map[nums1[i]]++;
}else{
num1_map[nums1[i]] = 1;
}
}
for(int i=0;i<num1_map.size();i++){
for(int j=0;j<num2_map.size();j++){
for(int k=0;k<num3_map.size();k++){
//寻找num4中是否存在与上述三个数相加等于0的值
if(num4_map.find(-nums1[i]-nums2[j]-nums3[k])!=num4_map.end()){
num += num4_map[nums4[i]];
}
}
}
}
return num;
}
};
优化二：使用四个map来存储
还是超时
class Solution {
public:
int fourSumCount(vector<int>& nums1, vector<int>& nums2, vector<int>& nums3, vector<int>& nums4) {
int num = 0;
unordered_map<int,int> num1_map;
unordered_map<int,int> num2_map;
unordered_map<int,int> num3_map;
unordered_map<int,int> num4_map;
for(int i=0;i<nums1.size();i++){
//如果这个数在map中
if(num1_map.find(nums1[i])!=num1_map.end()){
num1_map[nums1[i]]++;
}else{
num1_map[nums1[i]] = 1;
}
}
for(int i=0;i<nums2.size();i++){
//如果这个数在map中
if(num2_map.find(nums2[i])!=num2_map.end()){
num2_map[nums2[i]]++;
}else{
num2_map[nums2[i]] = 1;
}
}
for(int i=0;i<nums3.size();i++){
//如果这个数在map中
if(num3_map.find(nums3[i])!=num3_map.end()){
num3_map[nums3[i]]++;
}else{
num3_map[nums3[i]] = 1;
}
}
for(int i=0;i<nums4.size();i++){
//如果这个数在map中
if(num4_map.find(nums4[i])!=num4_map.end()){
num4_map[nums4[i]]++;
}else{
num4_map[nums4[i]] = 1;
}
}
//遍历每一个map
for(pair<int,int> kv1:num1_map){
for(pair<int,int> kv2:num2_map){
for(pair<int,int> kv3:num3_map){
for(pair<int,int> kv4:num4_map){
if(kv1.first+kv2.first+kv3.first+kv4.first==0){
num += kv1.second*kv2.second*kv3.second*kv4.second;
}
}
}
}
}
return num;
}
};
优化三：减少一个map循环，替换为查找
TMD，还是超时，乌鱼子
class Solution {
public:
int fourSumCount(vector<int>& nums1, vector<int>& nums2, vector<int>& nums3, vector<int>& nums4) {
int num = 0;
unordered_map<int,int> num1_map;
unordered_map<int,int> num2_map;
unordered_map<int,int> num3_map;
unordered_map<int,int> num4_map;
for(int i=0;i<nums1.size();i++){
//如果这个数在map中
if(num1_map.find(nums1[i])!=num1_map.end()){
num1_map[nums1[i]]++;
}else{
num1_map[nums1[i]] = 1;
}
}
for(int i=0;i<nums2.size();i++){
//如果这个数在map中
if(num2_map.find(nums2[i])!=num2_map.end()){
num2_map[nums2[i]]++;
}else{
num2_map[nums2[i]] = 1;
}
}
for(int i=0;i<nums3.size();i++){
//如果这个数在map中
if(num3_map.find(nums3[i])!=num3_map.end()){
num3_map[nums3[i]]++;
}else{
num3_map[nums3[i]] = 1;
}
}
for(int i=0;i<nums4.size();i++){
//如果这个数在map中
if(num4_map.find(nums4[i])!=num4_map.end()){
num4_map[nums4[i]]++;
}else{
num4_map[nums4[i]] = 1;
}
}
// for(int i=0;i<num1_map.size();i++){
// for(int j=0;j<num2_map.size();j++){
// for(int k=0;k<num3_map.size();k++){
// //寻找num4中是否存在与上述三个数相加等于0的值
// if(num4_map.find(-nums1[i]-nums2[j]-nums3[k])!=num4_map.end()){
// num += num4_map[nums4[i]];
// }
// }
// }
// }
//遍历每一个map
//优化：减少为三个循环
for(pair<int,int> kv1:num1_map){
for(pair<int,int> kv2:num2_map){
for(pair<int,int> kv3:num3_map){
// for(pair<int,int> kv4:num4_map){
// if(kv1.first+kv2.first+kv3.first+kv4.first==0){
// num += kv1.second*kv2.second*kv3.second*kv4.second;
// }
// }
if(num4_map.find(-kv1.first-kv2.first-kv3.first)!=num4_map.end()){
num += kv1.second*kv2.second*kv3.second*num4_map[-kv1.first-kv2.first-kv3.first];
}
}
}
}
return num;
}
};