LeetCode Top 100 高頻算法題系列的LeetCode算法題目就不幫大家翻譯了，程式設計師應該需要能看懂。LeetCode算法題有一個技巧：先看每道題的example，大部分情況看完example就能理解題目意思；如果看完example還有疑惑，可以再回過頭來看英文題目。這樣也可以節省一點時間~
Given an array nums of n integers, are there elements a, b, c in nums such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero.Notice that the solution set must not contain duplicate triplets.1th example
Input: nums = [-1,0,1,2,-1,-4]
Output: [[-1,-1,2],[-1,0,1]]
2th example
Input: nums = []
Output: []
3th example
Input: nums = [0]
Output: []
在LeetCode上本題屬於Medium難度。two Sum的升級版，不是很難，下面提供了2種解法，第一種解法的空間複雜度更低，下面是代碼和注釋，時間複雜度O(n *n)
class Solution { public List<List<Integer>> threeSum(int[] nums){ List<List<Integer>> res = new ArrayList<List<Integer>>(); Arrays.sort(nums); for(int i=0;i<nums.length-2;i++){//最後一組：length-3,length-2.length-1 nums[i]和i到length-1中搜索出和為-nums[i]的組合 if(nums[i]>0) return res; int low = i + 1; int high = nums.length-1; while(low<high){ int sum = nums[i]+nums[low]+nums[high]; if(sum==0){ List<Integer> l = new ArrayList<Integer>(); l.add(nums[i]); l.add(nums[low]); l.add(nums[high]); res.add(l); //nums[i]可能會出現兩種 -5 1...2....3....4 -5+1+4 和-5+2+3 while(low<high&&nums[low+1]==nums[low]) low++;
low++; high--; }else if(sum>0) high--; else low++; } while(i<nums.length-2&&nums[i+1]==nums[i]) i++; } return res; } /*public List<List<Integer>> threeSum(int[] nums) { List<List<Integer>> res = new ArrayList<List<Integer>>(); HashMap<Integer,Integer> map = new HashMap<Integer,Integer>(); Arrays.sort(nums); for(int i=0;i<nums.length;i++) map.put(nums[i],i); for(int i=0;i<nums.length-1;i++){ if(nums[i]>0)//當最小的值都大於0時，後面就不可能出現和為0的組合了 return res; for(int j=i+1;j<nums.length;j++){ if(nums[i]+nums[j]>0)//當前面兩個數和大於0，j之後的元素值只會更大，不可能出現負數 break; if(map.containsKey(-(nums[i]+nums[j]))){ int index = map.get(-(nums[i]+nums[j])); if(index>j){//保證不重複 List temp = new ArrayList<Integer>(); temp.add(nums[i]); temp.add(nums[j]); temp.add(nums[index]); res.add(temp); while(j<nums.length-1 && nums[j+1]==nums[j])//避免重複 j++; } } } while(i<nums.length-1 && nums[i+1]==nums[i])//避免重複 i++; } return res; }*/ }
長按，掃碼，關注
及時收看更多精彩內容
點擊」閱讀原文「：領取5T精品資料，面試總結、100+實戰項目
我知道你 「在看」