链接
https://leetcode-cn.com/problems/4sum/
耗时
解题：1 h 16 min 题解：6 min
题意
给定一个包含 n 个整数的数组 nums 和一个目标值 target，判断 nums 中是否存在四个元素 a，b，c 和 d ，使得 a + b + c + d 的值与 target 相等？找出所有满足条件且不重复的四元组。
注意：
答案中不可以包含重复的四元组。
思路
把四数之和看成 两数之和+两数之和。先处理出所有的两数之和，包括值和位置，存入哈希表；然后枚举两数之和，在哈希表里找 target-两数之和，如果能找到，则加入结果。
对于去重问题，我用的是 四元组排序后放入 set 去重。😦 想不出更好的方法了。
时间复杂度：
≫
O
(
n
2
)
\gg O(n^2)
≫O(n2)
AC代码
class Solution {
public:
vector
<vector
<int>> fourSum(vector
<int>& nums
, int target
) {
int n
= nums
.size();
unordered_map
<int, vector
<int>> unmp
;
for(int i
= 0; i
< n
; ++i
) {
for(int j
= i
+1; j
< n
; ++j
) {
unmp
[nums
[i
]+nums
[j
]].push_back(i
);
unmp
[nums
[i
]+nums
[j
]].push_back(j
);
}
}
vector
<vector
<int>> ans
;
set
<vector
<int>> res
;
for(int i
= 0; i
< n
; ++i
) {
for(int j
= i
+1; j
< n
; ++j
) {
int rest
= target
-nums
[i
]-nums
[j
];
if(unmp
.find(rest
) != unmp
.end()) {
auto tmp
= unmp
[rest
];
for(int k
= 0; k
< tmp
.size(); k
+=2) {
if(tmp
[k
] == i
|| tmp
[k
] == j
|| tmp
[k
+1] == i
|| tmp
[k
+1] == j
)
continue;
vector
<int> t
= {nums
[i
],nums
[j
],nums
[tmp
[k
]],nums
[tmp
[k
+1]]};
sort(t
.begin(), t
.end());
res
.insert(t
);
}
}
}
}
for(auto r
: res
) {
ans
.push_back(r
);
}
return ans
;
}
};
