遍历 num2 ，在 record 中查找是否有相同的元素（该元素的存储频率大于 0 ），如果有，用 map 容器resultVector 进行存储，同时该元素的频率减一。
动画描述// 空间复杂度: O(n)
class Solution {
public:
vector<int> intersect(vector<int>& nums1, vector<int>& nums2) {
map<int, int> record;
for(int i = 0 ; i < nums1.size() ; i ++){
record[nums1[i]] += 1;
}
vector<int> resultVector;
for(int i = 0 ; i < nums2.size() ; i ++){
if(record[nums2[i]] > 0){
resultVector.push_back(nums2[i]);
record[nums2[i]] --;
}
}
return resultVector;
}
};
7. 回旋镖的数量
题目来源于 LeetCode 上第 447 号问题： Number of Boomerangs 。
题目描述给定平面上 n 对不同的点，“回旋镖” 是由点表示的元组 (i, j, k) ，其中 i 和 j 之间的距离和 i 和 k 之间的距离相等（需要考虑元组的顺序）。
找到所有回旋镖的数量。你可以假设 n 最大为 500，所有点的坐标在闭区间 [-10000, 10000] 中。
题目解析n 最大为 500，可以使用时间复杂度为 O(n^2)的算法。
遍历所有的点，让每个点作为一个锚点
然后再遍历其他的点，统计和锚点距离相等的点有多少个
然后分别带入 n(n-1) 计算结果并累加到 res 中
注意点：
如果有一个点a，还有两个点 b 和 c ，如果 ab 和 ac 之间的距离相等，那么就有两种排列方法 abc 和 acb ；
如果有三个点b，c，d 都分别和 a 之间的距离相等，那么有六种排列方法，abc, acb, acd, adc, abd, adb；
如果有 n 个点和点 a 距离相等，那么排列方式为 n(n-1)；
计算距离时不进行开根运算, 以保证精度；
只有当 n 大于等于 2 时，res 值才会真正增加，因为当n=1时，增加量为1 * ( 1 - 1 ) = 0 。
动画描述// 空间复杂度: O(n)
class Solution {
public:
int numberOfBoomerangs(vector<pair<int, int>>& points) {
int res = 0;
for( int i = 0 ; i < points.size() ; i ++ ){
// record中存储 点i 到所有其他点的距离出现的频次
unordered_map<int, int> record;
for(int j = 0 ; j < points.size() ; j ++){
if(j != i){
// 计算距离时不进行开根运算, 以保证精度
record[dis(points[i], points[j])] += 1;
}
}
for(unordered_map<int, int>::iterator iter = record.begin() ; iter != record.end() ; iter ++){
res += (iter->second) * (iter->second - 1);
}
}
return res;
}
private:
int dis(const pair<int,int> &pa, const pair<int,int> &pb){
return (pa.first - pb.first) * (pa.first - pb.first) +
(pa.second - pb.second) * (pa.second - pb.second);
}
};
8. 四数相加 II
题目来源于 LeetCode 上第 454 号问题： 4Sum II 。
题目描述给定四个包含整数的数组列表 A , B , C , D ,计算有多少个元组 (i, j, k, l) ，使得 A[i] + B[j] + C[k] + D[l] = 0。