15. 3Sum

Problem Statement

Pattern: Pattern Two Pointer

---

2 Pointer Solution

public List<List<Integer>> threeSum (int[] num){
	Arrays.sort(num);
	List<List<Integer>> res = new LinkedList<>(); 
	for (int i = 0; i < num.length-2; i++) {
		if (i == 0 || (i > 0 && num[i] != num[i-1])) {
			int lo = i+1, hi = num.length-1, sum = 0 - num[i];
			while (lo < hi) {
				if (num[lo] + num[hi] == sum) {
					res.add(Arrays.asList(num[i], num[lo], num[hi]));
					while (lo < hi && num[lo] == num[lo+1]) lo++;
					while (lo < hi && num[hi] == num[hi-1]) hi--;
					lo++; hi--;
				} else if (num[lo] + num[hi] < sum) lo++;
				else hi--;
		   }
		}
	}
	return res;    
}

Notes

• simple solution like GFG Triplet Sum in Array

Set 2 Pointer Solution

Higher runtime

public List<List<Integer>> threeSum (int[] nums){
   Set<List<Integer>> lists = new HashSet<>();
   Arrays.sort(nums);
   for (int start = 0; start < nums.length-2; start++) {
   	int mid = start+1, end = nums.length-1;
   	while(mid < end) {
   		int sum = nums[start] + nums[mid] + nums[end];
   		if(sum < 0) mid++;
   		else if(sum > 0) end--;
   		else lists.add(Arrays.asList(nums[start], nums[mid++], nums[end--]));
   	}
   }
   return new ArrayList<>(lists);
}

here we can forego the duplicate logic. but the runtimme is much higher.