Similar to 3Sum, Use Two Pointers [Java] Easy-Understand
Problem\n\n> 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 uniqu
## Problem\n\n> 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`.\n\n**Note:** The solution set must not contain duplicate quadruplets.\n\n**Example:** \n\n```java\nGiven array nums = [1, 0, -1, 0, -2, 2], and target = 0.\n\nA solution set is:\n[\n  [-1,  0, 0, 1],\n  [-2, -1, 1, 2],\n  [-2,  0, 0, 2]\n]\n\nInput: [0, 0, 0, 0], and target = 0.\nOutput: [[0, 0, 0, 0]]\n```\n\n\n## Analysis\n\n### 3Sum + 4Sum\n\nUse two pointers in 3Sum.\n\n```java\npublic List<List<Integer>> fourSum(int[] nums, int target) {\n  int n = nums.length;\n  // sorting\n  Arrays.sort(nums);\n  // fourSum\n  List<List<Integer>> result = new ArrayList<>();\n  for (int i = 0; i < n; ++i) {\n    if (i > 0 && nums[i - 1] == nums[i]) continue;\n    threeSum(nums, i + 1, n - 1, target - nums[i], result);\n  }\n  return result;\n}\n  \nprivate void threeSum(int[] nums, int lo, int hi, int target, List<List<Integer>> result) {\n  int n = nums.length;\n  int subLen = hi - lo + 1;\n  for (int i = lo; i <= hi; ++i) {\n    if (i > lo && nums[i] == nums[i - 1]) continue;  // skip same result\n    // two pointers\n    int j = i + 1, k = hi;\n    int t = target - nums[i];\n    while (j < k) { // each element is only used once\n      if (nums[j] + nums[k] < t) {\n        ++j;\n      } else if (nums[j] + nums[k] > t) {\n        --k;\n      } else { // equal\n        result.add(Arrays.asList(nums[lo - 1], nums[i], nums[j], nums[k]));\n        ++j;\n        --k;\n        while (j < k && nums[j] == nums[j - 1]) j++;  // skip same result\n        while (j < k && nums[k] == nums[k + 1]) k--;  // skip same result\n      }\n    }\n  }\n}\n```\n\n**Time:** `O(N^3)`\n**Space:** `O(1)`\n\n\n\n
['Java']