🎓 Top 15 Udemy Courses (80-90% Discount): My Udemy Courses - Ramesh Fadatare — All my Udemy courses are real-time and project oriented courses.
▶️ Subscribe to My YouTube Channel (178K+ subscribers): Java Guides on YouTube
▶️ For AI, ChatGPT, Web, Tech, and Generative AI, subscribe to another channel: Ramesh Fadatare on YouTube
1. Introduction
This blog post addresses the Three Number Sum (3Sum) problem, a more complex variant of the Two Number Sum problem. The goal is to find all triplets in an array that sum up to a given target value.
Problem
Given an array of integers, find all triplets in the array that sum up to a given target value. In other words, for an array arr and a target value target, return all triplets a, b, c such that a + b + c = target.
Example:
Input array: [7, 12, 3, 1, 2, -6, 5, -8, 6]
Target sum: 0
Output: [[2, -8, 6], [3, 5, -8], [1, -6, 5]]
2. Solution Steps
1. Sort the array.
2. Use three-pointers to find triplets: one for the current element and two for finding a pair that sums up the complement of the current element.
3. For each element in the array, use a pair of pointers to scan the remaining part of the array to find pairs that sum up to the required value.
4. Move the pointers appropriately to avoid duplicates and find all the unique triplets.
5. Add each valid triplet to the result list.
6. Return the list of triplets.
3. Code Program
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
public class Solution {
// Main method for testing
public static void main(String[] args) {
int[] input = {7, 12, 3, 1, 2, -6, 5, -8, 6};
int targetSum = 0;
List<int[]> triplets = threeNumberSum(input, targetSum);
for (int[] triplet : triplets) {
System.out.println(Arrays.toString(triplet));
}
}
// Method to find all triplets with the given sum
public static List<int[]> threeNumberSum(int[] arr, int targetSum) {
Arrays.sort(arr);
List<int[]> triplets = new ArrayList<>();
for (int i = 0; i < arr.length - 2; i++) {
int left = i + 1;
int right = arr.length - 1;
while (left < right) {
int currentSum = arr[i] + arr[left] + arr[right];
if (currentSum == targetSum) {
triplets.add(new int[]{arr[i], arr[left], arr[right]});
left++;
right--;
} else if (currentSum < targetSum) {
left++;
} else if (currentSum > targetSum) {
right--;
}
}
}
return triplets;
}
}
Output:
[2, -8, 6] [3, 5, -8] [1, -6, 5]
Explanation:
For the input array [7, 12, 3, 1, 2, -6, 5, -8, 6] and target sum 0, the threeNumberSum method finds all the unique triplets whose sum is 0. It first sorts the array and then iterates through it, using two pointers to find pairs that, together with the current element, sum up to 0. The output triplets are [2, -8, 6], [3, 5, -8], and [1, -6, 5].
My Top and Bestseller Udemy Courses. The sale is going on with a 70 - 80% discount. The discount coupon has been added to each course below:
Build REST APIs with Spring Boot 4, Spring Security 7, and JWT
![[NEW] Learn Apache Maven with IntelliJ IDEA and Java 25](https://img-c.udemycdn.com/course/750x422/6852721_b512_2.jpg "[NEW] Learn Apache Maven with IntelliJ IDEA and Java 25")
[NEW] Learn Apache Maven with IntelliJ IDEA and Java 25
ChatGPT + Generative AI + Prompt Engineering for Beginners
Spring 7 and Spring Boot 4 for Beginners (Includes 8 Projects)
Available in Udemy for Business
Building Real-Time REST APIs with Spring Boot - Blog App
Available in Udemy for Business
Building Microservices with Spring Boot and Spring Cloud
Available in Udemy for Business
Java Full-Stack Developer Course with Spring Boot and React JS
Available in Udemy for Business
Build 5 Spring Boot Projects with Java: Line-by-Line Coding
Testing Spring Boot Application with JUnit and Mockito
Available in Udemy for Business
Spring Boot Thymeleaf Real-Time Web Application - Blog App
Available in Udemy for Business
Master Spring Data JPA with Hibernate
Available in Udemy for Business
Spring Boot + Apache Kafka Course - The Practical Guide
Available in Udemy for Business
Comments
Post a Comment
Leave Comment