7ms java code win over 100%


  • 125
    R

    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;
    	}

  • 0
    C
    This post is deleted!

  • 0
    C

    Hi rikimberley,

    Thanks for your sharing. It is very very very......brilliant solution. I am very impressive.


  • 1
    G

    Smart solution. Nice. Thanks for sharing.


  • 0
    G

    very smart algorithm,reduced so many unnecessary leaves


  • 1
    C

    very smart pruning method indeed!


  • 0
    D

    OMG this answer is killing everything


  • 7
    S

    Thank you very much! You let me see a new world.


  • 0
    R

    This is really creative thinking. Especially all the code to throw away impossible options and the idea to pass the selected numbers to the threeSum and twoSum methods.
    Good job!


  • 0
    C

    Brilliant! Most of solutions just iterate and check if the sum equals to the target.However, you just throw away all the impossible cases! Love your solution!


  • 0
    R

    Nice solution! I really want to know how much time have you spent for thinking of this solution?


  • 0

    I'm pretty impressed, very awesome idea. Thanks for sharing.


  • 10

    It's kind of ugly, but it works well. :)


  • 1
    M

    Great Solution. One question: In the loop of FourSum, does it have to get to the end of the array? What about stopping at two elements before the end where there is not enough numbers left?


  • 0
    X

    The beauty of coding, the beauty of intelligence.


  • 0
    W

    awesome solution ! very impressive.


  • 13
    M

    Awesome. Here is a generalized K Sum solution based on your idea. Got the same high performance.
    Using List<Integer> path to store the selected members, instead of passing them separately.

    List<List<Integer>> kSum_Trim(int[] a, int target, int k) {
        List<List<Integer>> result = new ArrayList<>();
        if (a == null || a.length < k || k < 2) return result;
        Arrays.sort(a);
        kSum_Trim(a, target, k, 0, result, new ArrayList<>());
        return result;
    }
    
    void kSum_Trim(int[] a, int target, int k, int start, List<List<Integer>> result, List<Integer> path) {
        int max = a[a.length - 1];
        if (a[start] * k > target || max * k < target) return;
        
        if (k == 2) {                        // 2 Sum
            int left = start;
            int right = a.length - 1;
            while (left < right) {
                if      (a[left] + a[right] < target) left++;
                else if (a[left] + a[right] > target) right--;
                else {
                    result.add(new ArrayList<>(path));
                    result.get(result.size() - 1).addAll(Arrays.asList(a[left], a[right]));
                    left++; right--;
                    while (left < right && a[left] == a[left - 1]) left++;
                    while (left < right && a[right] == a[right + 1]) right--;
                }
            }
        }
        else {                        // k Sum
            for (int i = start; i < a.length - k + 1; i++) {
                if (i > start && a[i] == a[i - 1]) continue;
                if (a[i] + max * (k - 1) < target) continue;
                if (a[i] * k > target) break;
                if (a[i] * k == target) {
                    if (a[i + k - 1] == a[i]) {
                        result.add(new ArrayList<>(path));
                        List<Integer> temp = new ArrayList<>();
                        for (int x = 0; x < k; x++) temp.add(a[i]);
                        result.get(result.size() - 1).addAll(temp);    // Add result immediately.
                    }
                    break;
                }
                path.add(a[i]);
                kSum_Trim(a, target - a[i], k - 1, i + 1, result, path);
                path.remove(path.size() - 1);        // Backtracking
            }
        }
    }
    

  • 5
    C

    翻译题,将以下句子翻译成英文:
    玩五阶魔方的思路就是从五阶降到四阶,然后再从四阶降到三阶,最后再按照玩三阶魔方的老套路解决问题。

    嗯,这个思路有点类似!


  • 1
    X

    @Cenyol The idea is to play the magic square of order five from five to four reduction of order, and then from four to three reduction in accordance with the order, then play the magic square of order three old routines to solve the problem.

    Well, it's a bit like this!


  • 1
    C

    @xiaoyesoso very good!


Log in to reply
 

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