15. 3Sum

Problem

Given an integer array nums, return all the triplets [nums[i], nums[j], nums[k]] 
such that i != j, i != k, and j != k, and nums[i] + nums[j] + nums[k] == 0.

Notice that the solution set must not contain duplicate triplets.

Example 1:
Input: nums = [-1,0,1,2,-1,-4]
Output: [[-1,-1,2],[-1,0,1]]
Explanation: 
nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0.
nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0.
nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0.
The distinct triplets are [-1,0,1] and [-1,-1,2].
Notice that the order of the output and the order of the triplets does not matter.

Example 2:
Input: nums = [0,1,1]
Output: []
Explanation: The only possible triplet does not sum up to 0.

Example 3:
Input: nums = [0,0,0]
Output: [[0,0,0]]
Explanation: The only possible triplet sums up to 0.
 
Constraints:
3 <= nums.length <= 3000
-105 <= nums[i] <= 105

Approach

• Muốn tìm triple (nums[i], nums[j], nums[k]) sao cho nums[i] + nums[j] + nums[k] = 0
• Nếu cố định 1 phần tử index i, thì ta cần tìm một cặp nums[j] and nums[k] sao cho nums[j] + nums[k] = -nums[i]. (Chính là bài 167. Two Sum II - Input Array Is Sorted)
• Và đối với bài toán này, việc sort mảng theo thứ tự tăng dần trước cũng không làm thay đổi kết quả, hỗ trợ việc tránh các kết quả trùng nhau theo yêu cầu the solution set must not contain duplicate triplets.

Ví dụ nums = [-1,0,1,2,-1,-4]
Sau khi sort ta có nums = [-4, -1, -1, 0, 1, 2]
Gỉa sử ta cố định nums[i] = -1, thì cần tìm nums[j] + nums[k] = 1, đó chính là cặp (0, 1) và (0, 2) => 2 triple tương ứng là [(-1,-1,2),(-1,0,1)]

Implementation

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        int n = nums.length;
        List<List<Integer>> result = new ArrayList<>();

        Arrays.sort(nums);

        for (int i = 0; i < n; i++) {
            if (i > 0 && nums[i] == nums[i-1]) continue; // avoid duplicate

            int target = -nums[i];
            int pLeft = i+1; int pRight = nums.length-1;
            if (pLeft >= n || pRight < 0 || pLeft == pRight) continue;

            // region two sum problem :))
            while (pLeft < pRight) {
                int leftVal = nums[pLeft]; int rightVal = nums[pRight];
                if (leftVal + rightVal == target) {
                    result.add(new ArrayList<>(Arrays.asList(nums[i], nums[pLeft], nums[pRight])));
                    do {
                        pLeft++;
                    } while (pLeft < n && nums[pLeft] == nums[pLeft-1]);// avoid duplicate
                    do {
                        pRight--;
                    } while (pRight >= 0 && nums[pRight] == nums[pRight+1]);// avoid duplicate
                } else if (leftVal + rightVal > target) {
                    do {
                        pRight--;
                    } while (pRight >= 0 && nums[pRight] == nums[pRight+1]);// avoid duplicate
                } else {
                    do {
                        pLeft++;
                    } while (pLeft < n && nums[pLeft] == nums[pLeft-1]);// avoid duplicate
                }
            }
        }

        return result;
    }
}