Array

Three sum from array

Pinterest LinkedIn Tumblr

Write a program to give three sums from the array.

Algorithm Explanation

Pass an array and sum to the utility function.
Use Hashmap to add the sum and index, array to increment index. Return the array of elements which give the sum equal to the sum of elements.
Print the return array.

Source Code

package com.dsacode.DataStructre.array;
 
import java.util.ArrayList;
import java.util.Arrays;
 
public class ThreeSumArray {
    public ArrayList < ArrayList < Integer > > threeSum(int[] num) {
        ArrayList < ArrayList < Integer > > result = new ArrayList < ArrayList < Integer > > ();
      
        if (num.length < 3)
            return result;
 
        Arrays.sort(num);
      
        for (int i = 0; i < num.length - 2; i++) {
            if (i == 0 || num[i] > num[i - 1]) {
      
                int negate = -num[i];
      
                int start = i + 1;
                int end = num.length - 1;
      
                while (start < end) {
                    if (num[start] + num[end] == negate) {
                        ArrayList < Integer > temp = new ArrayList < Integer >();
                        temp.add(num[i]);
                        temp.add(num[start]);
                        temp.add(num[end]);
      
                        result.add(temp);
                        start++;
                        end--;
 
                        while (start < end && num[end] == num[end + 1])
                            end--;
      
                        while (start < end && num[start] == num[start - 1])
                            start++;
                    } else if (num[start] + num[end] < negate) {
                        start++;
                    } else {
                        end--;
                    }
                }
      
            }
        }
      
        return result;
    }
    public static void main(String[] args) {
        int[] array={-1, 0, 1, 2, -1, -4};
        System.out.println("List of items form array: "+ Arrays.toString(array));
         
        ThreeSumArray ts= new ThreeSumArray();
        ArrayList < ArrayList < Integer > > res = ts.threeSum(array);
         
        System.out.println("Sum of two items '0' : "+ res.toString());
    }
 
}

Output

List of items form array: [-1, 0, 1, 2, -1, -4]
Sum of two items '0' : [[-1, -1, 2], [-1, 0, 1]]

Write A Comment