首页 > 代码库 > 3sum问题的解决
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.
For example, given array S = [-1, 0, 1, 2, -1, -4], A solution set is: [ [-1, 0, 1], [-1, -1, 2] ]
代码如下:算法复杂度O(n^2)
1 class Solution { 2 3 public List<List<Integer>> threeSum(int[] num) { 4 5 ArrayList<List<Integer>> result = new ArrayList<List<Integer>>(); 6 if (num == null || num.length < 3) 7 return result; 8 Arrays.sort(num); 9 int lastNum = num[0] - 1; 10 for (int i = 0; i < num.length - 2 && num[i] <= 0; i++) { 11 if (num[i] != lastNum) { 12 result.addAll(find(num, i)); 13 lastNum = num[i]; 14 } 15 } 16 return result; 17 } 18 19 private ArrayList<List<Integer>> find(int[] array, int index) { 20 21 int i = index + 1; 22 int j = array.length - 1; 23 int lastI = array[index] - 1; 24 int lastJ = array[index] - 1; 25 26 ArrayList<List<Integer>> Lists = new ArrayList<List<Integer>>(); 27 28 while (i < j) { 29 if (array[i] + array[j] + array[index] == 0) { 30 if (array[i] == lastI) { 31 i++; 32 } else if (array[j] == lastJ) { 33 j--; 34 } else { 35 lastI = array[i]; 36 lastJ = array[j]; 37 ArrayList<Integer> curList = new ArrayList<Integer>(); 38 curList.add(array[i]); 39 curList.add(array[j]); 40 curList.add(array[index]); 41 Lists.add(curList); 42 i++; 43 j--; 44 } 45 } else if (array[i] + array[j] + array[index] > 0) { 46 j--; 47 } else { 48 i++; 49 } 50 } 51 return Lists; 52 } 53 }
注意几点:
1,如果遇到重复的数字,那么可以直接跳过。外层循环和内层循环都可以,因为都是排过序的,如果遇到同样的数字必然产生同样的结果。
2,具体实现的时候直接让lastNum等于开始的数字减一,保证第一个数字不会被跳过。
算法的核心思路是,首先排序。这个算法复杂度是O(n*logn)。接下来先依次找每一个数字,每找到一个数字,剩下的目标就是在剩下的数字中找到2个数,使他们之和为0。正因为排过序,所以找两个数字的过程算法复杂度可以下降到O(n)。也就是从两头往中间。每次如果和大于0,就说明在外层数字确定的情况下,这两个数字的和大了,也就要让其变小,让j--,反之则i++。
3sum问题的解决
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。