4数之和

import java.util.Arrays;
import java.util.ArrayList;

public class Solution {
   ArrayList<ArrayList<Integer>> res= new ArrayList<ArrayList<Integer>>();
    int sum = 0;
    public ArrayList<ArrayList<Integer>> fourSum(int[] num, int target) {
        if(num == null || num.length < 4)
            return res;
        ArrayList<Integer> list =  new ArrayList<>();
        Arrays.sort(num);
        combine(num, target, 0, list);
        return res;
    }
//回溯法
    public void combine(int[] num, int target, int start, ArrayList<Integer> list){
        if(list.size() == 4 ){
            if(sum == target && !res.contains(list)){
                res.add(new ArrayList<>(list));
            }
            return;
        }
            for(int i = start; i < num.length; i++){
                sum += num[i];
                list.add(num[i]);
                combine(num, target, i + 1, list);
                sum -= list.get(list.size()-1);
                list.remove(list.size()-1);
            }
    }
}

public ArrayList<ArrayList<Integer>> fourSum(int[] num, int target) {
    Arrays.sort(num);  ArrayList<ArrayList<Integer>> res = new ArrayList<>();  backTrack(0, target, 0, num, res,new ArrayList<Integer>());  return res; } public void backTrack(int start, int target, int now, int[] num,  ArrayList<ArrayList<Integer>> res, ArrayList<Integer> temp) { if(temp.size()>4)return;  if (now == target && temp.size()==4)res.add(new ArrayList<Integer>(temp));  for (int i = start; i < num.length; i++) { if(i>start && num[i] == num[i-1])continue;  temp.add(num[i]);  now+=num[i];  backTrack(i+1,target,now,num,res,temp);  now-=num[i];  temp.remove(temp.size()-1);  }
}

超出内存是什么鬼

import java.util.*;
public class Solution {
    public ArrayList<ArrayList<Integer>> fourSum(int[] num, int target) {
        ArrayList<ArrayList<Integer>> res = new ArrayList<ArrayList<Integer>>();
        int n = num.length;
        if (num == null || n < 4) 
            return res;
        Arrays.sort(num);
        for(int i=0; i<n-3; i++) {
            int num1 = num[i];
            for(int j=i+1; j<n-2; j++) {
                int num2 = num[j];
                int left = j + 1;
                int right = n - 1;
                while(left < right) {
                    int sum = num[left] + num[right];
                    if(sum < target - num1 -num2) {
                        left++;
                    }
                    else if(sum > target - num1 -num2) {
                        right--;
                    }
                    else {
                        ArrayList<Integer> tmp = new ArrayList<Integer>();
                        int num3 = num[left];
                        int num4 = num[right];
                        tmp.add(num1);
                        tmp.add(num2);
                        tmp.add(num3);
                        tmp.add(num4);
                        res.add(tmp);
                        while(left < right && num[left] == num3)
                        	left++;
                    	while(right > left && num[right] == num4)
                        	right--;
                    }
                }
                while(j + 1 < n - 2 && num[j + 1] == num2)
                    j++;
            }
            while(i + 1 < n - 3 && num[i + 1] == num1)
                i++;
        }
		return res;
    }
}

The first time win over 100%. Basic idea is using subfunctions for 3sum and 2sum, and keeping throwing all impossible cases. O(n^3) time complexity, O(1) extra space complexity.

public List<List<Integer>> fourSum(int[] nums, int target) {
		ArrayList<List<Integer>> res = new ArrayList<List<Integer>>(); int len = nums.length; if (nums == null || len < 4) return res;

		Arrays.sort(nums); int max = nums[len - 1]; if (4 * nums[0] > target || 4 * max < target) return res; int i, z; for (i = 0; i < len; i++) {
			z = nums[i]; if (i > 0 && z == nums[i - 1])// avoid duplicate continue; if (z + 3 * max < target) // z is too small continue; if (4 * z > target) // z is too large break; if (4 * z == target) { // z is the boundary if (i + 3 < len && nums[i + 3] == z)
					res.add(Arrays.asList(z, z, z, z)); break;
			}

			threeSumForFourSum(nums, target - z, i + 1, len - 1, res, z);
		} return res;
	} /*
	 * Find all possible distinguished three numbers adding up to the target
	 * in sorted array nums[] between indices low and high. If there are,
	 * add all of them into the ArrayList fourSumList, using
	 * fourSumList.add(Arrays.asList(z1, the three numbers))
	 */ public void threeSumForFourSum(int[] nums, int target, int low, int high, ArrayList<List<Integer>> fourSumList, int z1) { if (low + 1 >= high) return; int max = nums[high]; if (3 * nums[low] > target || 3 * max < target) return; int i, z; for (i = low; i < high - 1; i++) {
			z = nums[i]; if (i > low && z == nums[i - 1]) // avoid duplicate continue; if (z + 2 * max < target) // z is too small continue; if (3 * z > target) // z is too large break; if (3 * z == target) { // z is the boundary if (i + 1 < high && nums[i + 2] == z)
					fourSumList.add(Arrays.asList(z1, z, z, z)); break;
			}

			twoSumForFourSum(nums, target - z, i + 1, high, fourSumList, z1, z);
		}

	} /*
	 * Find all possible distinguished two numbers adding up to the target
	 * in sorted array nums[] between indices low and high. If there are,
	 * add all of them into the ArrayList fourSumList, using
	 * fourSumList.add(Arrays.asList(z1, z2, the two numbers))
	 */ public void twoSumForFourSum(int[] nums, int target, int low, int high, ArrayList<List<Integer>> fourSumList, int z1, int z2) { if (low >= high) return; if (2 * nums[low] > target || 2 * nums[high] < target) return; int i = low, j = high, sum, x; while (i < j) {
			sum = nums[i] + nums[j]; if (sum == target) {
				fourSumList.add(Arrays.asList(z1, z2, nums[i], nums[j]));

				x = nums[i]; while (++i < j && x == nums[i]) // avoid duplicate ;
				x = nums[j]; while (i < --j && x == nums[j]) // avoid duplicate ;
			} if (sum < target)
				i++; if (sum > target)
				j--;
		} return;
	}