LeetCode 18. 4Sum

18. 4Sum

Difficulty: Medium

Given an array nums of n integers and an integer target, are there elements a, b, c, and d in nums such that a + b + c + d = target? Find all unique quadruplets in the array which gives the sum of target.

Note:

The solution set must not contain duplicate quadruplets.

Example:

Given array nums = [1, 0, -1, 0, -2, 2], and target = 0.

A solution set is:
[
  [-1,  0, 0, 1],
  [-2, -1, 1, 2],
  [-2,  0, 0, 2]
]

Solution

Language: Java

class Solution {
      public List<List<Integer>> fourSum(int[] nums, int target) {
            List<List<Integer>> result = new ArrayList<>();
            if (nums == null || nums.length == 0) {
                  return result;
           }
            Arrays.sort(nums);
            int n = nums.length;
            for (int m = 0; m < n - 3; m++) {
                  if (m > 0 && nums[m] == nums[m - 1]) {
                        continue;
                 }
                  for (int i = m + 1; i < n - 2; i++) {
                        if (i > m + 1 && nums[i] == nums[i - 1]) {
                              continue;
                       }
                        int j = i + 1;
                        int k = n - 1;
                        while (j < k) {
                              int res = nums[m] + nums[i] + nums[j] + nums[k];
                              if (res == target) {
                                    result.add(Arrays.asList(nums[m], nums[i], nums[j++], nums[k--]));
                                    while (j < k && nums[j] == nums[j - 1]) {
                                          j++;
                                   }
                                    while (j < k && nums[k] == nums[k + 1]) {
                                          k--;
                                   }
                             } else if (res > target) {
                                    k--;
                             } else {
                                    j++;
                             }
                       }
                 }
           }
            return result;
     }
}
​