18. 4Sum

Problem

Given an array nums of n integers, return an array of 
all the unique quadruplets [nums[a], nums[b], nums[c], nums[d]] such that:
- 0 <= a, b, c, d < n
- a, b, c, and d are distinct.
- nums[a] + nums[b] + nums[c] + nums[d] == target
You may return the answer in any order.

Example 1:
Input: nums = [1,0,-1,0,-2,2], target = 0
Output: [[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]
Example 2:

Input: nums = [2,2,2,2,2], target = 8
Output: [[2,2,2,2]]

Constraints:
1 <= nums.length <= 200
-109 <= nums[i] <= 109
-109 <= target <= 109

Intuition

• Tương tự bài 3sum, 2sum.
• Cần tìm một quadruplets, cố định 1 phần tử => có được bài toán 3sum

Approach

• Dùng 2 pointer duyệt đầu mảng và cuối mảng
• Độ phức tạp O(n3)
• Lưu ý có test case số lớn, nên lúc cộng trừ thì chuyển sang long

Implementation

class Solution {
    public List<List<Integer>> fourSum(int[] nums, int target) {
        List<List<Integer>> result = new ArrayList<>();

        Arrays.sort(nums);
        
        for (int i = 0; i < nums.length; i++) {
            if (i > 0 && nums[i] == nums[i-1]) continue;

            // 3sum problem
            for (int j = i+1; j < nums.length; j++) {
                if (j > (i+1) && nums[j] == nums[j-1]) continue;

                long newTarget = (long)target - nums[i] - nums[j]; // use long datatype to avoid overflow number
                int pLeft = j+1; int pRight = nums.length-1;
                if (pLeft >= nums.length || pRight < j+1) continue;

                // 2sum problem
                while (pLeft < pRight) {
                    long sum = nums[pLeft] + nums[pRight]; // use long datatype to avoid overflow number
                    if (sum == newTarget) {
                        result.add(new ArrayList<>(Arrays.asList(nums[i], nums[j], nums[pLeft], nums[pRight])));
                        do {
                            pRight--;
                        } while (pRight >= j+1 && nums[pRight] == nums[pRight+1]);
                        do {
                            pLeft++;
                        } while (pLeft < nums.length && nums[pLeft] == nums[pLeft-1]);
                    } else if (sum > newTarget) {
                        do {
                            pRight--;
                        } while (pRight >= j+1 && nums[pRight] == nums[pRight+1]);
                    } else {
                        do {
                            pLeft++;
                        } while (pLeft < nums.length && nums[pLeft] == nums[pLeft-1]);
                    }
                }
            }
        }

        return result;
    }
}