3Sum
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.
Note:
The solution set must not contain duplicate triplets.
Example:
Given array nums = [-1, 0, 1, 2, -1, -4], A solution set is: [ [-1, 0, 1], [-1, -1, 2] ]
class Solution {
public List<List<Integer>> threeSum(int[] nums) {
if (nums.length < 3) return new ArrayList<>();
Arrays.sort(nums);
Set<List<Integer>> triplet= new HashSet<>();
for (int i = 0; i < nums.length - 2; i++) {
int j = i + 1;
int k = nums.length - 1;
while (j < k) {
int sum = nums[i] + nums[j] + nums[k];
if (sum == 0) triplet.add(Arrays.asList(nums[i], nums[j++], nums[k--]));
else if (sum > 0) k--;
else if (sum < 0) j++;
}
}
return new ArrayList<>(triplet);
}
}Here, we are going to solve using three variables iteratively. j iterates from beginning and k iterates from end. If array length is less than 3, then return a new arraylist. Below are steps to be followed.,
1) Sort the array.
2) Create a set with list of integer as a type. Our overall return type must be List<List> but reason behind to use Set is to avoid duplicates of triplets.
3) For each i,
a) j is i+1, k is nums.length-1
b) sum variable is overall sum of nums[i], nums[j], nums[k].
c) If sum is equal to 0, then add those triplets(nums of i, j, k) to triplet set as a list.
d) Else if sum less than 0, increment j by 1,
e) Else if sum greater than 0, decrement k by 1.
f) Repeat above all from step 3, until i reaches length - 2(i.e. to find last triplet)
4) Finally return triplet set in a new arraylist.
Below is sample working given for one iteration
nums - [-1,0,1,2,-1,-4]
sorted - [-4,-1,-1,0,1,2]
n = 6
Loop for: i = 0
j = 1, k = 5
sum = -4 + -1 + 2 = -3 < 0 , j++
j = 2, k = 5
sum = -4 + -1 + 2 = -3 < 0 , j++
j = 3, k = 5
sum = -4 + 0 + 2 = -2 < 0, j++
j = 4, k = 5
sum = -4 + 1 + 2 = -1 < 0 , j++
sorted - [-4,-1,-1,0,1,2]
n = 6
Loop for: i = 0
j = 1, k = 5
sum = -4 + -1 + 2 = -3 < 0 , j++
j = 2, k = 5
sum = -4 + -1 + 2 = -3 < 0 , j++
j = 3, k = 5
sum = -4 + 0 + 2 = -2 < 0, j++
j = 4, k = 5
sum = -4 + 1 + 2 = -1 < 0 , j++
Like this iteration will goes on...
Related Post:
Click here for April month challenges with solution and explanation
😍..Happy Coding...😍
Click Follow button to receive latest updates from us instantly.
Please let us know about your views in comment section.
Help Others, Please Share..!!!!
Comments
Post a Comment