3Sum problem Leetcode https://leetcode.com/problems/3sum/
2Sum problem deals with 2 numbers. the target is given. while going through the array , the another number is derived from subtracting the current number from target . we save numbers in a map if the number present in the map we can get the sum(target) by adding the 2 numbers.
Get kasan kulasekaram’s stories in your inbox
Join Medium for free to get updates from this writer.
But 3Sum problem deals with 3 numbers. the target is given . in 2sum we can predict the two numbers in advance .but in 3sum we can only predict the sum of the 2 numbers out of 3.
the diagram above explains how to solve the 3sum problem.I followed the above steps in my code below here
class Solution {
public List<List<Integer>> threeSum(int[] nums) {
List<List<Integer>> list = new ArrayList<>();
Arrays.sort(nums);
int sum = 0;
int target = 0;
int left =0;
int right=0;
for(int i=0;i<nums.length-2;i++){
if((i-1)>=0 && nums[i]==nums[i-1])continue;
target = -nums[i];
left = i+1;
right = nums.length-1;
while(left<right){
sum = nums[left]+nums[right];
if(target==sum){
List<Integer> l = new ArrayList<Integer>();
l.add(nums[left]);
l.add(nums[right]);
l.add(nums[i]);
list.add(l);
while(left<right && nums[left]==nums[left+1] && nums[right]==nums[right-1]){
left++;
right — ;
}
left++;
right — ;
}else if(target<sum){
right — ;
}else{
left++;
}
}
}
return list;
}
}
