Tags: leetcode two pointers java
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.1
This solution will result in Time Limit Exceeded since it has complexity of O(n3). We can naively check for all combination of array in three nested loops.
| class Solution { | |
| public List<List<Integer>> threeSum(int[] nums) { | |
| List<List<Integer>> result = new ArrayList<>(); | |
| if (nums.length < 3){ | |
| return result; | |
| } | |
| Arrays.sort(nums); | |
| Set<String> unique = new HashSet<>(); | |
| for (int i = 0; i < nums.length; i++) { | |
| for (int j = i + 1; j < nums.length; j++) { | |
| for (int k = j + 1; k < nums.length; k++) { | |
| if (nums[i] + nums[j] + nums[k] == 0 ){ | |
| String seq = "" + nums[i] + nums[j] + nums[k]; | |
| if (!unique.contains(seq)) { | |
| List<Integer> temp = new ArrayList<>(Arrays.asList(nums[i], nums[j], nums[k])); | |
| result.add(temp); | |
| unique.add(seq); | |
| } | |
| } | |
| } | |
| } | |
| } | |
| return result; | |
| } | |
| } |
Using two pointer solution, we can acheive O(n2) time complexity.
| class Solution { | |
| public List<List<Integer>> threeSum(int[] nums) { | |
| List<List<Integer>> result = new ArrayList<List<Integer>>(); | |
| HashSet<Integer> track = new HashSet<>(); | |
| Arrays.sort(nums); | |
| for(int i = 0; i < nums.length - 2; i++) { | |
| int fix = nums[i]; | |
| int start = i + 1; | |
| int end = nums.length - 1; | |
| if (i > 0 && nums[i] == nums[i - 1]) { | |
| continue; | |
| } | |
| while (start < end ) { | |
| int sum = fix + nums[start] + nums[end]; | |
| if (start > i + 1 && (nums[start] == nums[start - 1])) { | |
| start = start + 1; | |
| continue; | |
| } | |
| if (sum == 0) { | |
| List<Integer> tempResult = new ArrayList<>(Arrays.asList(fix, nums[start], nums[end])); | |
| result.add(tempResult); | |
| start = start + 1; | |
| end = end - 1; | |
| } | |
| else if (sum > 0) { | |
| end = end - 1; | |
| } else { | |
| start = start + 1; | |
| } | |
| } | |
| } | |
| return result; | |
| } | |
| } |