每天一题LeetCode[第十天]

2019-11-08 02:37:14

字体：大中小

来源：转载

供稿：网友

每天一题LeetCode[第十天]

3Sum

Description:

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: 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]]

解题思路：

首先我想能不能用map的思想提高效率，取a+b的相反数，作为索引值，细想了一下，发现很复杂，很麻烦。所以看了Top Solution ，发现思路应该是这样的。。。采用预排序方法，先对Array进行排序，可以复杂的为o(nlogn) 。接着在已排序的数组，可以一个个往前推进的去穷举，然后记得要去排除一些明显不可能项降低复杂度，但是最终复杂度还是o(n^2)

由于现在在外面旅游，所以时间会拉下，但是要补回来

java代码：

public List<List<Integer>> threeSum(int [] nums){ if(null==nums || nums.length<3){ return Collections.emptyList(); } List<List<Integer>> res=new ArrayList<>(); //先排序 Arrays.sort(nums); for(int i=0;i<nums.length-2;i++){ if(i==0 || (i>0 && nums[i]!=nums[i-1])) { int low=i+1,high=nums.length-1,sum=0-nums[i]; while (low > high) { //查找以i为下标的TRIANGLE if (nums[low] + nums[high] == sum) { res.add(Arrays.asList(nums[i], nums[low], nums[high])); while (low < high && nums[low] == nums[low + 1]) { low++; } while (low < high && nums[high] == nums[high - 1]) { high--; } low++; high--; } else if (nums[low] + nums[high] < sum) { low++; } else { high--; } } } } return res; }

提高代码质量就是：积累精美的思路，优质的细节的过程。

上一篇：使用指针变量作为函数参数

下一篇：重拾算法之剑指Offier——从上往下打印二叉树