Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- class 3SumProblem {
- Map<Integer, HashSet<Integer>> entryIndexMap = new HashMap<>();
- public List<List<Integer>> threeSum(int[] nums) {
- Arrays.sort(nums);
- List<List<Integer>> sumList = new ArrayList<>();
- for (int i = 0; i < nums.length; i++) {
- int num = nums[i];
- HashSet<Integer> indices = entryIndexMap.get(num);
- if (indices != null) {
- indices.add(i);
- } else {
- indices = new HashSet<>();
- indices.add(i);
- entryIndexMap.put(num, indices);
- }
- }
- for (int i = 0; i < nums.length - 1; i++) {
- // We are skipping the parts where there is repeated continuous values of i and j. Because these are going to lead to repeated solution
- if (!(i > 0 && nums[i] == nums[i - 1])) {
- for (int j = i + 1; j < nums.length; j++) {
- if (!(j > i + 1 && nums[j] == nums[j - 1])) {
- int sum = nums[i] + nums[j];
- int remaining = 0 - sum;
- if (entryIndexMap.get(remaining) != null) {
- Set<Integer> indices = entryIndexMap.get(remaining);
- for (int index : indices) {
- if (index > i && index > j) {
- List<Integer> list = new ArrayList<>();
- list.add(nums[i]);
- list.add(nums[j]);
- list.add(nums[index]);
- sumList.add(list);
- break;
- }
- }
- }
- }
- }
- }
- }
- return sumList;
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement