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)
A:
即使是用先把两个加起来,然后,再找第三个的方式,复杂度也是O(n^2)阿。还有更简单的吗?
----------------第一遍自己写的,写了100多行, 比较SB,就删掉了,反正也不会再看---------
--------这是第三遍-----------------------
public class threeSome { public List<List<Integer>> threeSum(int[] num) { List<List<Integer>> all = new LinkedList<List<Integer>>(); if(num == null || num.length <3) return all; Arrays.sort(num); int n = num.length; for(int i=0;i<n-2;i++){ if(i!=0 && num[i] == num[i-1]) continue; int j=i+1, k = n-1; while(j<k){ while(j<k && num[i]+num[j]+num[k] >0) k--; if( j<k && num[i]+num[j]+num[k] == 0 ){ List<Integer> al = new LinkedList<Integer>(); al.add(num[i]); al.add(num[j]); al.add(num[k]); all.add(al); } while(j<k && num[j+1]==num[j]) j++; j++; } } return all; } }声明List of List时,new 后面的语句中,第一层<>里面的不能写成LinkedList的
Mistakes:
1 :
if (num[k] < 0) continue;这里,本来写的是,当num[k]<0的时候,是继续往下跑,而不是跳出,的
哎,还是对break, continue的理解不够深啊。---- 对自己的算法,也是理解不够清楚。
2:其实对于unique2方法,可以不用考虑三个0的情况,就只允许最多三个重复的就行。记得到最后检测重复即可。
所谓的two Pointer 算法。
Given two arrays (A and B) sorted in ascending order, and an integer x. we need to find i and j, such that a[i] + b[j] is equal to X. i and j our pointers, at first step i is points to the first element of a, and j points to the last element of b. i = 0; j = b.size() - 1; move first pointer one by one through the array a, and correct position of the second pointer if needed while (i < a.size()) { while(a[i] + b[j] > X && j > 0) j--; if (a[i] + b[j] == X) writeAnswer(i, j); i++; } Also, there was the same question in Russian, maybe it can helps. link to google-translated version http://codeforces.ru/blog/entry/4136
下面这个SB方法,就是简单地遍历所有的可能,先排序,然后3个runner都从前往后跑,第一个必须<0 >0 然后加入时,和刚刚加入的,对比,如果一样,就不加。否则加入到结果里。
---------------------第三遍的代码,精简了些---------------- Idea: o(n^2) solution exists. First sort the array, and then from left to right, for each num[i], search the pair that sums up to -num[i] using Two Sum algorithm.
public class Solution { public ArrayList<ArrayList<Integer>> threeSum(int[] num) { ArrayList<ArrayList<Integer>> all = new ArrayList<ArrayList<Integer>>(); ArrayList<Integer> al; int n = num.length; Arrays.sort(num); for(int first =0;first<n-2;first++) { int target = -num[first]; // then following is the 2 sum int i = first + 1; int j = n - 1; while (i < j) { while (i < j && num[i] + num[j] >= target) { if (num[i] + num[j] == target) { al = new ArrayList<Integer>(); al.add(num[first]); al.add(num[i]); al.add(num[j]); if( all.isEmpty() ) all.add(al); else{ ArrayList<Integer> preList = all.get(all.size()-1); if(preList.get(1) != al.get(1) || preList.get(2)!=al.get(2)){ all.add(al); } } } j--; } i++; } while(first+1<n-2 && num[first+1] == num[first]) first++; } return all; } }
---------------- we do not need the repeat of "first" value at all. ---------------------------
Then by checking the last two elements is not equal, we guarantee no duplicate.
-------------------------第二遍--------------对a进行遍历的时候,分开处理3个a全等, 2个a相等和 只有1个a的情况(这时候,需要用到2sum)
public class Solution { public ArrayList<ArrayList<Integer>> threeSum(int[] num) { ArrayList<ArrayList<Integer>> all = new ArrayList<ArrayList<Integer>>(); Arrays.sort(num); boolean threeZero = false; // if we find a=b=c=0 for (int i = 0; i < num.length - 2; i++) { // test the case that 3 A[i] in a row and they are all == 0 if (num[i] == num[i + 1] && num[i] == num[i + 2]) {// if (num[i] == 0) threeZero = true; continue; } // now deal with the case that two value of num[i] if (num[i] == num[i + 1]) { for (int j = i + 2; j < num.length; j++) if (num[i] + num[i + 1] + num[j] == 0) { add2All(num[i], num[i + 1], num[j], all); break; } continue; } // Now, num[i] is the only appearance,we can use two pointer // algorithm twoSum(num, i + 1, -num[i], all); // two sum ,by adding num[i] back } if (threeZero) { add2All(0, 0, 0, all); } return all; } ArrayList<ArrayList<Integer>> twoSum(int[] num, int begin, int target, ArrayList<ArrayList<Integer>> all) { // NOTE: num is already sorted int i = begin, j = num.length - 1; while (i < j) { // update i so that num[newI] is the last appearance of num[i] boolean flag = false; // whether num[i] is half of target while (i < j && num[i + 1] == num[i]) { if (num[i] + num[i + 1] == target) { flag = true; } i++; } if (flag)// if we have num = 0 , 2,2,3, begin == 1, target = 4 add2All(-target, num[i - 1], num[i], all); while (j > i && num[i] + num[j] >= target) { if (num[i] + num[j] == target) { add2All(-target, num[i], num[j], all); break; } j--; } i++; // update i to the next } return all; } void add2All(int a, int b, int c, ArrayList<ArrayList<Integer>> all) { ArrayList<Integer> al = new ArrayList<Integer>(); al.add(a); al.add(b); al.add(c); all.add(al); } }
No comments:
Post a Comment