本文共 5393 字,大约阅读时间需要 17 分钟。
我的LeetCode代码仓:
原题链接:
题目描述:
知识点:哈希表,对撞双指针
三重循环遍历nums数组。时间复杂度是O(n ^ 3),其中n为数组nums的长度。空间复杂度是O(1)。
JAVA代码:
public class Solution { public List
> threeSum(int[] nums) { int n = nums.length; List
> listList = new ArrayList<>(); Arrays.sort(nums); for(int i = 0; i < n; i++) { if(nums[i] > 0) { break; } if(i > 0 && nums[i] == nums[i - 1]) { continue; } for(int j = i + 1; j < n; j++) { if(nums[i] + nums[j] > 0) { break; } if(j > i + 1 && nums[j] == nums[j - 1]) { continue; } for(int k = j + 1; k < n; k++) { if(nums[i] + nums[j] + nums[k] > 0) { break; } if(k > j + 1 && nums[k] == nums[k - 1]) { continue; } if(nums[i] + nums[j] + nums[k] == 0) { List list = new ArrayList<>(); list.add(nums[i]); list.add(nums[j]); list.add(nums[k]); listList.add(list); } } } } return listList; }}
我们用一个哈希表来存储数组中出现的所有元素及其出现的次数。
我们总共分三种情况:
(1)三个数字相同:如果0这个数字在哈希表中记录的次数等于或者大于3次,那么3个0是一个组合,将其记录在结果中。
(2)两个数字相同:在我们用哈希表记录了数组中所有元素及其出现的次数以后,我们就可以对数组进行过滤,将重复的元素剔除掉得到一个新的数组集合ArrayList,里面没有重复元素。对这个集合进行一次排序操作。再用双重循环遍历集合。
a.当arrayList.get(i) * 2 + arrayList.get(j) == 0且在哈希表中arrayList.get(i)出现的次数大于等于2次。
b.当arrayList.get(i) + arrayList.get(j) * 2 == 0且在哈希表中arrayList.get(j)出现的次数大于等于2次。
(3)三个数字都不同:在哈希表中- arrayList.get(i) - arrayList.get(j)出现的次数大于等于1次且- arrayList.get(i) - arrayList.get(j) > arrayList.get(j)。
将上述三种情况的结果都保存在结果中,最终返回总结果即可。
这个思路过程中生成哈希表这一过程的时间复杂度是O(n),其中n为数组的长度。排序arrayList集合的时间复杂度是O(mlogm),其中m为数组中不重复元素的个数。遍历arrayList的时间复杂度是O(m ^ 2)。而空间复杂度由于使用了哈希表,一定是O(n)级别的。
JAVA代码:
public class Solution { public List
> threeSum(int[] nums) { List
> listList = new ArrayList<>(); HashMap hashMap = new HashMap<>(); for(int i = 0; i < nums.length; i++) { if(hashMap.containsKey(nums[i])) { hashMap.put(nums[i], hashMap.get(nums[i]) + 1); }else { hashMap.put(nums[i], 1); } } if(hashMap.containsKey(0) && hashMap.get(0) >= 3) { addToListList(0, 0, 0, listList); } ArrayList arrayList = new ArrayList<>(); for (Integer integer : hashMap.keySet()) { arrayList.add(integer); } Collections.sort(arrayList); for(int i = 0; i < arrayList.size(); i++) { for(int j = i + 1; j < arrayList.size(); j++) { if(arrayList.get(i) * 2 + arrayList.get(j) == 0 && hashMap.get(arrayList.get(i)) >= 2) { addToListList(arrayList.get(i), arrayList.get(i), arrayList.get(j), listList); } if(arrayList.get(i) + arrayList.get(j) * 2 == 0 && hashMap.get(arrayList.get(j)) >= 2) { addToListList(arrayList.get(i), arrayList.get(j), arrayList.get(j), listList); } int num = - arrayList.get(i) - arrayList.get(j); if(num > arrayList.get(j) && hashMap.containsKey(num)) { addToListList(arrayList.get(i), arrayList.get(j), num, listList); } } } return listList; } private void addToListList(int num1, int num2, int num3, List
> listList) { List list = new ArrayList<>(); list.add(num1); list.add(num2); list.add(num3); listList.add(list); }}
LeetCode解题报告:
(1)首先对数组nums进行从小到大排序,此步骤可以调用Java中的库函数Arrays.sort()。
(2)设置一个索引指针i依次从左到右遍历排序之后的nums数组。
(3)对于每一个nums[i],我们假设nums[i]是所要寻找的三个数中的最小数。那么如果nums[i] > 0,显然在本次循环中不可能找到另外两个数num[left]和nums[right],使得满足条件nums[left] + nums[right] == 0 - nums[i],我们直接break结束整个循环。
(4)如果i > 1且nums[i] == nums[i - 1],那么所找到的三个数的组合一定是一样的,我们直接continue跳过本轮i循环的后面的所有语句,直接i++进入下一轮循环。
(5)设置left的初值为i + 1,right的初值为nums.length() - 1。当left < right时,我们可以一直寻找nums[left]和nums[right]这两个值。因此我们可以再在for循环内部设置一个while循环,条件是while(left < right)。
(6)如果nums[left] + nums[right] == 0 - nums[i],那么我们找到了一组三个数,我们将这三个数保存起来,并且令left++,right--。此时我们需要注意题目的要求:答案中不可以包含重复的三元组,因此如果left++以后的nums[left]和之前的nums[left]相等且满足条件left < right的话,我们依旧需要设置一个循环另left++,直到找到一个不同的元素为止。同理对right--进行同样的操作,如果right--以后的nums[right]和之前的nums[right]相等且满足条件left < right的话,我们依旧需要right--。
(7)如果nums[left] + nums[right] > 0 - nums[i],那么说明所寻找的两数太大了,我们需要进行right--的操作。同理为了避免重复三元组的出现,我们需要进行(6)中对right指针的操作。
(8)如果nums[left] + nums[right] < 0 - nums[i],那么说明所寻找的两数太小了,我们需要进行left++的操作。同理为了避免重复三元组的出现,我们需要进行(6)中对left指针的操作。
首先,我们有一个排序过程,是O(nlog(n))级别的复杂度,其中n为nums数组的长度。而对于对撞双指针,我们的时间复杂度可以看成是O(n)级别的,而其外面还有一个指针在遍历整个数组,因此总的时间复杂度是O(n ^ 2)级别的。空间复杂度是O(1)级别的,整个过程中我们没有使用额外的空间。
JAVA代码:
public class Solution { public List
> threeSum(int[] nums) { List
> listList = new ArrayList<>(); Arrays.sort(nums); for(int i = 0; i < nums.length - 2; i++) { if(nums[i] > 0) { break; } if(i > 0 && nums[i] == nums[i - 1]) { continue; } int left = i + 1; int right = nums.length - 1; while(left < right) { if(nums[i] + nums[left] + nums[right] == 0) { List list = new ArrayList<>(); list.add(nums[i]); list.add(nums[left]); list.add(nums[right]); listList.add(list); left++; right--; while(left < right && nums[left] == nums[left - 1]) { left++; } while(left < right && nums[right] == nums[right + 1]) { right--; } }else if(nums[i] + nums[left] + nums[right] < 0) { left++; while(left < right && nums[left] == nums[left - 1]) { left++; } }else { right--; while(left < right && nums[right] == nums[right + 1]) { right--; } } } } return listList; }}
LeetCode解题报告: