LeetCode 3Sum

Question

Given an integer array nums, return all the triplets [nums[i], nums[j], nums[k]] such that i != j, i != k, and j != k, and nums[i] + nums[j] + nums[k] == 0. Notice that the solution set must not contain duplicate triplets.

Brute force

We can run 3 loops to check each possible triplets, we also need to eliminate the duplicates from both sides. this method will work but will work but will give time limit exceed after time constraints. To do this in given time limit we need to sort the array first and Create a loop that fixes the left most integer. This reduces the problem to 2sum for remaining array. For each loop iteration where duplicates are skipped, we need to do a left/right iteration using while loop. my code:

	class Solution {
	public List<List<Integer>> threeSum(int[] nums) {
	List<List<Integer>> li=new ArrayList<>();
	Arrays.sort(nums);
	for(int i=0;i<nums.length-2;i++){
	if(i>0&&nums[i]==nums[i-1]){
	continue;
	}
	else{
	int l=i+1;
	int r=nums.length-1;
	while(l<r){
	if(nums[i]+nums[l]+nums[r]==0){
	List<Integer> li1=new ArrayList<Integer>();
	li1.add(nums[i]);
	li1.add(nums[l]);
	li1.add(nums[r]);
	li.add(li1);
	r--;
	while(r>=0&&nums[r]==nums[r+1]){
	r--;
	}
	}
	else if(nums[i]+nums[l]+nums[r]>0){
	r--;
	}
	else{
	l++;
	}
	}
	}
	}
	return li;
	}
	}

view raw 3sum hosted with ❤ by GitHub