每天一題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——從上往下打印二叉樹