首页 > 代码库 > Leetcode: 3Sum
Leetcode: 3Sum
Given an array S of n integers, are there elements a, b, c in S such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero.Note:Elements in a triplet (a,b,c) must be in non-descending order. (ie, a ≤ b ≤ c)The solution set must not contain duplicate triplets. For example, given array S = {-1 0 1 2 -1 -4}, A solution set is: (-1, 0, 1) (-1, -1, 2)
难度:84, 我一开始采用brute force的方法,也就是NP做法,类似Combination Sum, Path Sum之类枚举的方法,结果毫不留情地在big case的时候TLE了,毕竟这里brute force复杂度O(N^3)。寻思无奈,看了一下别人的思路,Code Ganker提供了一种方法,先sort array, 然后3个元素中的一个元素num[i]从大到小遍历,另外两个元素用-num[i]作 target用Two Sum来找对应的集合。这里Two Sum 肯定不用brute force, 那样这里就O(N^2)了,也不用HashMap, 比较复杂。用夹逼方法来做,O(N),当找到一个加起来为target的组合后,还不要忘了要skip一下重复的元素来节省时间。总的时间复杂度为O(NlongN + N^2) = O(N^2)
1 public class Solution { 2 public ArrayList<ArrayList<Integer>> threeSum(int[] num) { 3 ArrayList<ArrayList<Integer>> res = new ArrayList<ArrayList<Integer>>(); 4 if (num == null || num.length < 3) { 5 return res; 6 } 7 Arrays.sort(num); 8 for (int i=num.length-1; i>=2; i--) { 9 if (i<num.length-1 && num[i]==num[i+1]) continue;10 ArrayList<ArrayList<Integer>> sumOfTwo = twoSum(num, 0, i-1, -num[i]);11 for (int k=0; k<sumOfTwo.size(); k++) {12 ArrayList<Integer> temp = sumOfTwo.get(k);13 temp.add(num[i]);14 }15 res.addAll(sumOfTwo);16 }17 return res;18 }19 20 public ArrayList<ArrayList<Integer>> twoSum(int[] num, int l, int r, int target) {21 ArrayList<ArrayList<Integer>> sets = new ArrayList<ArrayList<Integer>>();22 while (l < r) {23 if (num[l] + num[r] == target) {24 ArrayList<Integer> set = new ArrayList<Integer>();25 set.add(num[l]);26 set.add(num[r]);27 sets.add(new ArrayList<Integer>(set));28 l++;29 r--;30 while (l<r && num[l]==num[l-1]) {31 l++;32 }33 while (l<r && num[r]==num[r+1]) {34 r--;35 }36 }37 else if (num[l] + num[r] > target) {38 r--;39 }40 else {41 l++;42 }43 }44 return sets;45 }46 }
Leetcode: 3Sum
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。