# [LeetCode] 018. 4Sum (Medium) (C++/Java/Python)

Github:
https://github.com/illuz/leetcode

## 018.4Sum (Medium)

### 分析：

1. 跟之前的 2Sum, 3Sum 和 3Sum Closest 1样的做法，先排序，再左右夹逼，复杂度 O(n^3)。不过用 Python 可能会被卡超时。
2. 先求出每两个数的和，放到 `HashSet` 里，再利用之前的 2Sum 去求。这类算法比较快，复杂度 O(nnlog(n))，不过细节要处理的很多。

`itertools` 的1些用法。

### 代码：

C++:

class Solution {
public:
vector<vector<int> > fourSum(vector<int> &num, int target) {
vector<vector<int> > ret;
int len = num.size();

if (len <= 3)
return ret;

sort(num.begin(), num.end());

for (int i = 0; i <= len – 4; i++) {
for (int m = i + 1; m <= len – 3; m++) {
int j = m + 1;
int k = len – 1;
while (j < k) {
if (num[i] + num[m] + num[j] + num[k] < target) {
++j;
} else if (num[i] + num[m] + num[j] + num[k] > target) {
–k;
} else {
ret.push_back({ num[i], num[m], num[j], num[k] });
++j;
–k;
while (j < k && num[j] == num[j – 1])
++j;
while (j < k && num[k] == num[k + 1])
–k;
}
}
while (m < len && num[m] == num[m + 1])
++m;
}
while (i < len && num[i] == num[i + 1])
++i;
}

return ret;
}
};

Java:

public class Solution {
public List<List<Integer>> fourSum(int[] num, int target) {
List<List<Integer>> ret = new ArrayList<List<Integer>>();
HashMap<Integer, List<Integer[]>> hm = new HashMap<Integer, List<Integer[]>>();
int len = num.length;

Arrays.sort(num);
// store pair
for (int i = 0; i < len – 1; ++i) {
for (int j = i + 1; j < len; ++j) {
int sum = num[i] + num[j];
Integer[] tuple = {num[i], i, num[j], j};
if (!hm.containsKey(sum)) {
hm.put(sum, new ArrayList<Integer[]>());
}
}
}

Integer[] keys = hm.keySet().toArray(new Integer[hm.size()]);
for (int key : keys) {
if (hm.containsKey(key)) {
if (hm.containsKey(target – key)) {
List<Integer[]> first_pairs = hm.get(key);
List<Integer[]> second_pairs = hm.get(target – key);

for (int i = 0; i < first_pairs.size(); ++i) {
Integer[] first = first_pairs.get(i);
for (int j = 0; j < second_pairs.size(); ++j) {
Integer[] second = second_pairs.get(j);
// check
if (first[1] != second[1] && first[1] != second[3] &&
first[3] != second[1] && first[3] != second[3]) {
List<Integer> ans = Arrays.asList(first[0], first[2], second[0], second[2]);
Collections.sort(ans);
if (!ret.contains(ans)) {
}
}
}
}

hm.remove(key);
hm.remove(target – key);
}
}
}

return ret;
}
}

Python:

import collections
import itertools
class Solution:
# @return a list of lists of length 4, [[val1,val2,val3,val4]]
def fourSum(self, num, target):
two_sum = collections.defaultdict(list)
ret = set()
for (id1, val1), (id2, val2) in itertools.combinations(enumerate(num), 2):
two_sum[val1 + val2].append({id1, id2})
keys = two_sum.keys()
for key in keys:
if two_sum[key] and two_sum[target – key]:
for pair1 in two_sum[key]:
for pair2 in two_sum[target – key]:
if pair1.isdisjoint(pair2):
ret.add(tuple(sorted([num[i] for i in pair1 | pair2])))
del two_sum[key]
if key != target – key:
del two_sum[target – key]
return [list(i) for i in ret]

1. 本站所有资源来源于用户上传和网络，如有侵权请邮件联系站长！
2. 分享目的仅供大家学习和交流，您必须在下载后24小时内删除！
3. 不得使用于非法商业用途，不得违反国家法律。否则后果自负！
4. 本站提供的源码、模板、插件等等其他资源，都不包含技术服务请大家谅解！
5. 如有链接无法下载、失效或广告，请联系管理员处理！
6. 本站资源售价只是赞助，收取费用仅维持本站的日常运营所需！
7. 本站源码并不保证全部能正常使用，仅供有技术基础的人学习研究，请谨慎下载
8. 如遇到加密压缩包，请使用WINRAR解压,如遇到无法解压的请联系管理员！