日本搞逼视频_黄色一级片免费在线观看_色99久久_性明星video另类hd_欧美77_综合在线视频

國內最全IT社區平臺 聯系我們 | 收藏本站
阿里云優惠2
您當前位置:首頁 > php開源 > php教程 > [LeetCode] 018. 4Sum (Medium) (C++/Java/Python)

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

來源:程序員人生   發布時間:2015-03-13 08:36:16 閱讀次數:3843次

索引:[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 ,找出4個數 a,b,c,d 使得a + b + c + d = target

分析

  1. 跟之前的 2Sum, 3Sum 和 3Sum Closest 1樣的做法,先排序,再左右夾逼,復雜度 O(n^3)。不過用 Python 可能會被卡超時。
  2. 先求出每兩個數的和,放到 HashSet 里,再利用之前的 2Sum 去求。這類算法比較快,復雜度 O(nnlog(n)),不過細節要處理的很多。

這里 C++ 用的是算法1, Java, Python 用的是 2。
這題 Java 可以好好地學學 HashMap 的使用, Python 可以學習 set, collectionitertools 的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[]>()); } 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]


生活不易,碼農辛苦
如果您覺得本網站對您的學習有所幫助,可以手機掃描二維碼進行捐贈
程序員人生
------分隔線----------------------------
分享到:
------分隔線----------------------------
關閉
程序員人生
主站蜘蛛池模板: 国产精品久久久久久久久久白浆 | 91久久久久久久久 | 午夜男人网 | 欧美日韩第一区 | 欧美日韩另类一区 | 亚洲综合在线播放 | 亚洲国产精品成人久久久 | 成人在线视频一区 | 成人影音 | 在线看黄色av | 亚洲色图19p | 成人在线不卡 | 精品久久中文 | 色又黄又爽18件免费网站 | 日本乱轮视频 | 久9精品| 国内精品一区二区三区视频 | 欧美日韩在线一区二区三区 | 日韩福利在线 | 国产v亚洲v天堂无码 | 91网站视频在线观看 | 久久国产一区 | 91精品国产综合久久蜜臀 | 蜜桃永久免费 | 亚洲欧美综合 | 国产精品久久久久久久久久久免费看 | 高清国产一区二区三区四区五区 | 国产女主播在线视频 | 国产精品久久久av | 国产在线看片 | 亚洲精品99久久久久中文字幕 | 欧美亚洲综合在线 | 美女久久久久 | 日韩久久久精品 | 亚洲最大毛片 | 日本在线看片 | 久久久久国产精品一区三寸 | 中文字幕av一区二区三区 | 日韩视频在线观看 | 国产超碰人人做人人爽aⅴ 亚州国产 | 成人在线免费观看视频 |