首页 > 代码库 > Leetcode-3Sum
Leetcode-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.
Note:
- Elements in a triplet (a,b,c) must be in non-descending order. (ie, a ≤ b ≤ c)
- 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)Have you met this question in a real interview?
Analysis:
Solution:
1 public class Solution { 2 public List<List<Integer>> threeSum(int[] num) { 3 List<List<Integer>> resList = new ArrayList<List<Integer>>(); 4 if (num.length<3) return resList; 5 6 Arrays.sort(num); 7 Map<Integer,Integer> numMap = new HashMap<Integer,Integer>(); 8 for (int i=0;i<num.length;i++) 9 if (numMap.containsKey(num[i]))10 numMap.put(num[i],numMap.get(num[i])+1);11 else numMap.put(num[i],1);12 13 int first = 0;14 int second = -1;15 while (first<num.length-2){ 16 numMap.put(num[first],numMap.get(num[first])-1);17 second = first+1;18 while (second<num.length-1){19 numMap.put(num[second],numMap.get(num[second])-1);20 int left = 0-num[first]-num[second];21 if (left>=num[second] && numMap.containsKey(left) && numMap.get(left)>0){22 List<Integer> temp = new LinkedList<Integer>();23 temp.add(num[first]);24 temp.add(num[second]);25 temp.add(left);26 resList.add(temp);27 }28 numMap.put(num[second],numMap.get(num[second])+1);29 if (left<num[second]) break;30 while (second< num.length-1 && num[second]==num[second+1]) second++;31 second++;32 }33 numMap.put(num[first],numMap.get(num[first])+1);34 while (first<num.length-2 && num[first]==num[first+1]) first++;35 first++;36 37 }38 39 return resList; 40 }41 }
NOTE: There is a way to solve this problem without using hashmap. Practice it!
Leetcode-3Sum
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。