3Sum — Leetcode
2 min readJul 20, 2023
Topic: Array
Difficulty: Medium
Question Number: 15
To understand this question better, first solve 2sum problem of leetcode
2sum- leetcode
Problem statement:
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.
Explanation:
Approach
- Sort the input array.
- Iterate over the input array to fix the value in tempsum.
- Take two pointers, one(start) at i + 1 and the other(end) at n — 1.
- If the sum is smaller than tempsum, shift the start pointer to the right.
- Else, If the sum is bigger, shift the end pointer to the left.
- Else, if the sum of elements at i, start, end are equal to zero then store it in res.
- To eliminate the redundancy shift the start and end pointer unless you get a value not equal to the previous value.
- Return the res as the answer.
Code:
class Solution {
public List<List<Integer>> threeSum(int[] nums) {
List<List<Integer>> res= new ArrayList<>();
if(nums == null || nums.length == 0) return res;
Arrays.sort(nums);
if(nums[0] >0) return res;
int N = nums.length;
for(int i=0; i< N; i++) {
int start=i+1;
int end=N-1;
if(i>0 && nums[i]==nums[i-1]) continue;
while(start<end) {
//handle duplicate
int tempSum = nums[i] + nums[start] + nums[end];
if(tempSum == 0) {
res.add(Arrays.asList(new Integer[]{nums[i], nums[start], nums[end]}));
start++;
end--;
while(start< end && nums[start] == nums[start-1]) start++;
while(start< end && nums[end] == nums[end+1]) end--;
} else if (tempSum > 0) end--;
else start++;
}
}
//handle duplicate
return res;
}
}
Thank You
Oshi Raghav