Three Sum

Summary

The Three Sum problem is a classic algorithmic challenge that involves finding three distinct elements in an array that sum up to zero. This problem requires a combination of sorting, two-pointer technique, and sliding window approach to find the triplets. The key concepts involved are sorting, two-pointers, and sliding windows.

Detailed Explanation

The problem statement can be interpreted as follows: given an integer array nums with n elements, find all unique triplets in nums that sum up to zero. Note that each element in the triplet should appear only once.

To solve this problem, we will follow these steps:

First, sort the array nums in ascending order.
Initialize three pointers: i, j, and k. Set i = 0, j = i + 1, and k = n - 1.
Move the j pointer to the right until it meets the k pointer or a valid triplet is found.
For each valid triplet, add it to the result list and move the i and j pointers accordingly.
Repeat steps 2-4 until all possible triplets are exhausted.

Here's an ASCII art diagram illustrating the two-pointer approach:

       +---------------+
       |     i      |
       +---------------+
                  |
                  |  j = i + 1
                  v
       +---------------+
       |    k (n - 1)  |
       +---------------+

Time complexity: O(n^2) Space complexity: O(1)

Optimized Solutions

Java

public List<List<Integer>> threeSum(int[] nums) { Arrays.sort(nums); List<List<Integer>> result = new ArrayList<>(); for (int i = 0; i < nums.length - 2; i++) { if (i > 0 && nums[i] == nums[i - 1]) continue; int j = i + 1, k = nums.length - 1; while (j < k) { int sum = nums[i] + nums[j] + nums[k]; if (sum < 0) { j++; } else if (sum > 0) { k--; } else { result.add(Arrays.asList(nums[i], nums[j], nums[k])); while (j < k && nums[j] == nums[j + 1]) j++; while (j < k && nums[k] == nums[k - 1]) k--; j++; k--; } } } return result; }