[LeetCode] 018. 4Sum (Medium) (C++/Java/Python)
发布时间：2020-12-13 20:15:49 所属栏目：PHP教程 来源：网络整理
导读：索引：[LeetCode] Leetcode 题解索引 (C/Java/Python/Sql) Github: https://github.com/illuz/leetcode 018.4Sum (Medium) 链接 ： 题目：https://oj.leetcode.com/problems/4sum/ 代码(github)：https://github.com/illuz/leetcode 题意 ： 给1个数列 S,找
|
索引：[LeetCode] Leetcode 题解索引 (C++/Java/Python/Sql) 018.4Sum (Medium)链接：题目：https://oj.leetcode.com/problems/4sum/ 题意：给1个数列 S,找出4个数 a,b,c,d 使得 分析：
这里 C++ 用的是算法1， Java,Python 用的是 2。 代码：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,j};
if (!hm.containsKey(sum)) {
hm.put(sum,new ArrayList<Integer[]>());
}
hm.get(sum).add(tuple);
}
}
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)) {
ret.add(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]
（编辑：李大同） 【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容! |