Triplet Sum in Array Problem GFG
Given an array arr[] and an integer target, determine if there exists a triplet in the array whose sum equals the given target.
Return true if such a triplet exists, otherwise, return false.
Examples
Input: arr[] = [1, 4, 45, 6, 10, 8], target = 13
Output: true
Explanation: The triplet {1, 4, 8} sums up to 13
Input: arr[] = [1, 2, 4, 3, 6, 7], target = 10
Output: true
Explanation: The triplets {1, 3, 6} and {1, 2, 7} both sum to 10.
Input: arr[] = [40, 20, 10, 3, 6, 7], target = 24
Output: false
Explanation: No triplet in the array sums to 24
Constraints:
3 ≤ arr.size() ≤ 103
1 ≤ arr[i] ≤ 105
Approach 1
//{ Driver Code Starts
import java.io.*;
import java.util.*;
class Main {
public static void main(String args[]) throws IOException {
BufferedReader read = new BufferedReader(new InputStreamReader(System.in));
int t = Integer.parseInt(read.readLine().trim()); // Read number of test cases
while (t-- > 0) {
String line = read.readLine().trim(); // Read the array input
String[] numsStr = line.split(" "); // Split the input string by spaces
int[] nums =
new int[numsStr.length]; // Convert string array to integer array
for (int i = 0; i < numsStr.length; i++) {
nums[i] = Integer.parseInt(numsStr[i]);
}
int target = Integer.parseInt(read.readLine().trim()); // Read target sum
Solution ob = new Solution();
boolean ans =
ob.hasTripletSum(nums, target); // Call the function and store result
System.out.println(ans ? "true" : "false"); // Output the result
}
}
}
// } Driver Code Ends
// User function Template for Java
class Solution {
// Should return true if there is a triplet with sum equal
// to x in arr[], otherwise false
public static boolean hasTripletSum(int arr[], int target) {
// Your code Here
int n=arr.length;
for(int i=0;i<n;i++)
{
HashSet<Integer> st= new HashSet<>();
for(int j=i+1;j<n;j++)
{
int third=target-(arr[i]+arr[j]);
if(st.contains(third))
{
// List<Integer> temp= Arrays.asList(arr[i],arr[j],third);
return true;
}
st.add(arr[j]);
}
}
return false;
}
}
Approach: Sorting + Two Pointers
import java.util.Arrays;
class Solution {
public static boolean hasTripletSum(int arr[], int target) {
int n = arr.length;
Arrays.sort(arr); // Step 1: Sort the array
for (int i = 0; i < n - 2; i++) {
int left = i + 1, right = n - 1;
while (left < right) {
int sum = arr[i] + arr[left] + arr[right];
if (sum == target) {
return true; // Found a valid triplet
} else if (sum < target) {
left++; // Increase sum by moving left pointer right
} else {
right--; // Decrease sum by moving right pointer left
}
}
}
return false; // No triplet found
}
}
Comments
Post a Comment