Created
November 5, 2018 03:19
-
-
Save sogwiz/0f72f2bda527b14089993f94a83c7660 to your computer and use it in GitHub Desktop.
3sum
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
class Solution { | |
public List<List<Integer>> threeSum(int[] nums) { | |
Set<List<Integer>> combos = new HashSet<List<Integer>>(); | |
Arrays.sort(nums); | |
Map<Integer, Integer> values = new HashMap<Integer,Integer>(); | |
for(int i = 0; i<nums.length;i++){ | |
if(values.containsKey(nums[i])){ | |
values.put(nums[i],values.get(nums[i])+1); | |
}else{ | |
values.put(nums[i],1); | |
} | |
} | |
for(int i = 0 ; i<nums.length-2; i++){ | |
if(nums[i]<=0){ | |
for(int j = i+1; j<nums.length-1; j++){ | |
if(nums[i]+nums[j]<=0){ | |
int keyNeeded = -1*(nums[i]+nums[j]); | |
if(values.containsKey(keyNeeded) ){ | |
boolean shouldAdd = false; | |
//now we need to ensure we have enough counts | |
if(keyNeeded==nums[i]||keyNeeded==nums[j]){ | |
if(nums[i]==0){ | |
if (values.get(0)>2){ | |
//we're good here | |
shouldAdd = true; | |
} | |
}else if(values.get(keyNeeded)>1){ | |
//we're good here | |
shouldAdd = true; | |
} | |
}else { | |
shouldAdd = true; | |
} | |
if (shouldAdd){ | |
List<Integer> | |
validCombo = Arrays.asList(nums[i],nums[j],keyNeeded); | |
Collections.sort(validCombo); | |
combos.add(validCombo); | |
} | |
} | |
}else{ | |
break; | |
} | |
} | |
}else { | |
break; | |
} | |
} | |
List<List<Integer>> list = new ArrayList<List<Integer>>(); | |
Iterator<List<Integer>> iter = combos.iterator(); | |
while(iter.hasNext()){ | |
list.add(iter.next()); | |
} | |
return list; | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment