4Sum

Problem: 4Sum

The solution is similar to 3 Sum problem. We need to use some methods to implement early return. Besides, we shall also avoid duplicate answers.

Code in Python:

class Solution(object):
    def fourSum(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[List[int]]
        """
        nums = sorted(nums)
        n = len(nums)
        ans = []
        for i in xrange(n-3):
            if nums[i] + nums[i+1] + nums[i+2] + nums[i+3] > target:
                break
            if i > 0 and nums[i] == nums[i-1]:
                continue
            for j in xrange(i+1, n-2):
                if j > i+1 and nums[j] == nums[j-1]:
                    continue
                l, r = j+1, n-1
                while l < r:
                    sum = nums[i]+nums[j]+nums[l]+nums[r]
                    if sum == target:
                        ans.append([nums[i], nums[j], nums[l], nums[r]])
                        l += 1
                        r -= 1
                        while l < r and nums[l] == nums[l-1]: l += 1
                        while r > l and nums[r] == nums[r+1]: r -= 1
                    elif sum < target:
                        l += 1
                        while l < r and nums[l] == nums[l-1]: l += 1
                    else:
                        r -= 1
                        while r > l and nums[r] == nums[r+1]: r -= 1
        return ans

Code in Java:

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

        if (nums.length < 4) return res;

        Arrays.sort(nums);

        for (int i = 0; i < nums.length-3; i++) {
            if (i > 0 && nums[i] == nums[i-1])
                continue;
            for (int j = i+1; j < nums.length-2; j++) {
                if (j > i+1 && nums[j] == nums[j-1])
                    continue;
                int l = j+1, r = nums.length-1;
                while (l < r) {
                    if (nums[i]+nums[j]+nums[l]+nums[r] == target) {
                        List<Integer> quadruplet = new ArrayList<Integer>();
                        quadruplet.add(nums[i]);
                        quadruplet.add(nums[j]);
                        quadruplet.add(nums[l]);
                        quadruplet.add(nums[r]);
                        res.add(quadruplet);
                        while (l+1 < nums.length && nums[l+1] == nums[l])
                            l++;
                        l++;
                        while (r-1 >= 0 && nums[r-1] == nums[r])
                            r--;
                        r--;
                    } else if (nums[i]+nums[j]+nums[l]+nums[r] < target) {
                        while (l+1 < nums.length && nums[l+1] == nums[l])
                            l++;
                        l++;
                    } else {
                        while (r-1 >= 0 && nums[r-1] == nums[r])
                            r--;
                        r--;
                    }
                }
            }
        }

        return res;
    }
}

Also we can use some tricks to reduce running time, like the solution here.