首页 > 代码库 > Leetcode: 3Sum

Leetcode: 3Sum

2024-07-25 23:56:00   219人阅读

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


联系
我们