JAVA O(n^2) Solution by reducing 4SUM to 3SUM

• ``````public class Solution {

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

if (nums == null || nums.length < 4) {
return res;
}

Arrays.sort(nums);
int len = nums.length;

if (nums[0] * 4 > target || nums[len - 1] * 4 < target) {
return res;
}

int n;
for (int i = 0; i < len; i ++) {
n = nums[i];
if (i > 0 && n == nums[i - 1]) continue;
if (n + 3 * nums[len - 1] < target) continue;
if (4 * n > target) break;
if (4 * n == target) {
if (i + 3 < len && nums[i + 3] == nums[i]) {
}
break;
}

int [] subSum = Arrays.copyOfRange(nums, i + 1, len);
List<List<Integer>> rem = threeSum(subSum, target - n);

if (rem.size() != 0) {
for (List<Integer> subList : rem) {
}
}
}

return res;
}

//3Sum: O(n), because not need to Arrays.sort again in this method;
public List<List<Integer>> threeSum(int[] nums, int target) {
List<List<Integer>> res = new ArrayList<>();

if (nums == null || nums.length == 0) {
return res;
}

// Arrays.sort(nums);

int sum;
int lo,hi;

for (int i = 0; i < nums.length - 2; i ++) {
if (i > 0 && nums[i] == nums[i - 1]) {
continue;
}
sum = target - nums[i];

lo = i + 1;
hi = nums.length - 1;

while (lo < hi) {
if (nums[lo] + nums[hi] == sum) {

while (lo < hi && nums[lo] == nums[lo + 1]) lo++;
while (hi > lo && nums[hi] == nums[hi - 1]) hi--;

lo++;
hi--;
}else if (nums[lo] + nums[hi] < sum) {
lo ++;
}else {
hi --;
}
}
}
return res;
}
}
``````

• threeSum is still O(n^2) not O(n)
So it is O(n^3)

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.