Leetcode 18: 4Sum

For example, given array S = [1, 0, -1, 0, -2, 2], and target = 0.

A solution set is:
[
  [-1,  0, 0, 1],
  [-2, -1, 1, 2],
  [-2,  0, 0, 2]
]

Code

class Solution(object):
    def fourSum(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[List[int]]
        """
        
        if len(nums) < 4: 
            return []

        res = []
        nums = sorted(nums)

        for i in xrange(len(nums)-3):
            if i > 0 and nums[i-1] == nums[i]:
                continue
            for j in xrange(i+1, len(nums)-2):
                if j > i+1 and nums[j-1] == nums[j]:
                    continue
                m, n = j+1, len(nums)-1
                while m < n:
                    if nums[i]+nums[j]+nums[m]+nums[n] == target:
                        res.append((nums[i], nums[j], nums[m], nums[n]))
                        while m < n and nums[m] == nums[m+1]:
                            m += 1
                        while m < n and nums[n] == nums[n-1]:
                            n -=1
                        m += 1
                        n -= 1
                    elif nums[i]+nums[j]+nums[m]+nums[n] < target:
                        m += 1
                    else:
                        n -= 1

        return res
        

Idea

As usual, sort the array first. Then create four indices, i, j, m and n. Every time, fix i and j and move m and n as to approach target. Be very careful about dealing with duplicates. (line 16-17, 19-20, 25-28).

Also see 2Sum and 3Sum. 

Reference: https://discuss.leetcode.com/topic/12368/clean-accepted-java-o-n-3-solution-based-on-3sum/2