iframe-proxy | Sunbelt Computer Software

146 lines (134 loc) · 4.58 KB
class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        if (nums.length < 3) return new ArrayList<>(); // if nums less than 3 element
        Arrays.sort(nums); // sort array
        Set<List<Integer>> set = 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) set.add(Arrays.asList(nums[i], nums[j++], nums[k--]));
                else if (sum > 0) k--;
                else if (sum < 0) j++;
        return new ArrayList<>(set);
*************************************************************************************************
class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> res=new ArrayList<>();
                Arrays.sort(nums);
        for(int i=0;i<nums.length-2;i++)
            if(i==0 || (i>0 && nums[i]!=nums[i-1]))
                int lo=i+1,hi=nums.length-1;
                int target=0-nums[i];
                while(lo<hi)
                    int sum=nums[lo]+nums[hi];
                    if(sum==target)
                        res.add(Arrays.asList(nums[i],nums[lo],nums[hi]));
                        while(lo<hi && nums[lo]==nums[lo+1])lo++;
                        while(lo<hi && nums[hi]==nums[hi-1])hi--;
                    else if(sum>target)
        return res;
***********************************************************************
    Video explanation: https://youtu.be/1aQvO4JPo70
class Solution {
    public static List<List<Integer>> threeSum(int[] nums) {
       List<List<Integer>> result = new ArrayList<List<Integer>>();
    	if(nums == null || nums.length < 3)
        	return result;
    	// sort the array in-place
    	Arrays.sort(nums);
    	for (int i = 0; i < nums.length - 2; i++) {
    	    if (i == 0 || (i > 0 && nums[i] != nums[i-1])) {
    	        int low = i+1, high = nums.length - 1;
    	        int sum = 0 - nums[i];
                // Finding two sum using two pointer
    	        while (low < high) {
    	           if (nums[low] + nums[high] == sum) {
    	              result.add(Arrays.asList(nums[i], nums[low], nums[high]));
                      // if next number is duplicates skip that
    	              while (low < high && nums[low] == nums[low+1]) low++;
                      // if previous number is duplicates skip that
    	              while (low < high && nums[high] == nums[high-1]) high--;
    	              low++; 
		              high--;
    	           } else if (nums[low] + nums[high] < sum) {
    	              low++;
    	           } else {
    	              high--;
       return result;
***************************************************************************
//Two pointer Solution
//Sort the array
//Get an element from the array
//Find it has pair from the remaining elements of the array
class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        Arrays.sort(nums);
        List<List<Integer>> triplets = new ArrayList();
        for(int i=0; i<nums.length-2; i++)
            if(i>0 && nums[i] == nums[i-1])  //To skip the same element
                continue;
            searchPair(-nums[i], i+1, nums, triplets); 
        return triplets;
    public static void searchPair(int target, int left, int[] arr, List<List<Integer>> triplets)
        int right = arr.length-1;
        while(left < right)
            int currentSum = arr[left] + arr [right];
            if(currentSum == target)
                triplets.add(Arrays.asList(-target, arr[left], arr[right]));
                left++;
                right--;
                while(left<right && arr[left] == arr[left-1]) //skip the same element
                    left++;
                while(left<right && arr[right] == arr[right+1]) //skip the same element
                    right--;
            else if(target > currentSum)
                left++;
            else
                right--;
Sunbelt Computer Software

PL/B Language Development and Support

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

Sunbelt Computer Software

PL/B Language Development and Support

FilesExpand file tree

015_ThreeSum15.java

Latest commit

History

015_ThreeSum15.java

File metadata and controls
