3 Sum Problem Solution | 100 Days of Code Day 10

3Sum.java

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> sol = new ArrayList<>();
        // To sort the values as we will consider skipping them if same, to avoid duplicates
        Arrays.sort(nums);
        for(int i = 0; i< nums.length-2; i++) {
            if(nums[i] > 0) {
                break;
            }
            if(i>0 && nums[i] == nums[i-1]) {
                // comparing with previous. If both are same, 
                // then skip to avoid duplicate triplets
                continue;
            }
            Set<Integer> set = new HashSet<>(); // set because it can retreive in O(1)
            int target = -nums[i];
            for(int j = i+1; j < nums.length; j++) {
                int rem = target - nums[j];
                if(set.contains(rem)) { // here we are retrieving from set in O(1)
                    // we found our triplet. Hence adding to the sol
                    sol.add(Arrays.asList(nums[i], nums[j], rem));
                    if(j< nums.length-1 && nums[j] == nums[j+1]) {
                        // skipping duplicate values while considering for triplets
                        j++;
                    }
                } else {
                    set.add(nums[j]);
                }
            }
        }
        return sol;
    }
}