For a given
array find a1, a2 and a3 such that a1+a2+a3
= x.
We can solve
this problem by sorting the array, and apply following logic.
Fix one element in array (a1) and scan the array using two pointers one from
beginning and other from end of the array to find a2 and a3.
import java.util.*; public class TripletSum { public List<String> getSum(int arr[], int sum){ List<String> result = new ArrayList<> (); Arrays.sort(arr); for(int i=0; i<arr.length; i++){ int a1 = arr[i]; int remSum = sum-a1; int leftCounter = i+1, rightCounter=arr.length-1; while(leftCounter < rightCounter){ if(arr[leftCounter] + arr[rightCounter] == remSum){ result.add(a1 + "," + arr[leftCounter] + "," + arr[rightCounter]); } if(arr[leftCounter] + arr[rightCounter] < remSum) leftCounter++; else rightCounter--; } } return result; } }
public class TripletSumTest { public static void main(String arg[]){ TripletSum tripletSum = new TripletSum(); System.out.println(tripletSum.getSum(new int[]{1, 4, 45, 6, 10, 8}, 22)); System.out.println(tripletSum.getSum(new int[]{2, 4, 6, 8, 10, 12, 14}, 16)); } }
No comments:
Post a Comment