18. 4Sum

# Medium

Similar to #15 3Sum problem.

Two index(fixed) pointers(i: 0 to len(nums)-3; j: i+1 to len(nums)-2) and two flexible pointers(z: j+1; k: len(nums)-1).

In order to avoid duplication, check duplicated number immediately after the two for loops.

Python

class Solution(object):
    def fourSum(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[List[int]]
        """
        # edge case
        if len(nums) < 4:
            return []
        
        # regular case
        result = set()
        nums2 = sorted(nums)
        for i in range(len(nums2)-3):
            if i > 0 and nums2[i] == nums2[i-1]:
                continue
            for j in range(i+1, len(nums2)-2):
                if j > i+1 and nums2[j] == nums2[j-1]:
                    continue
                z = j + 1
                k = len(nums2) - 1
                while z < k:
                    s = nums2[i] + nums2[j] + nums2[z] + nums2[k]
                    if s == target:
                        temp = (nums2[i], nums2[j], nums2[z], nums2[k])
                        result.add(temp)
                        z += 1
                        k -= 1
                    elif s > target:
                        k -= 1
                    else:
                        z += 1
        
        return result

Time complexity = $O(n^3)$ , space complexity = $O(1)$ .

It can be extended to kSum problem. Time complexity = $O(n^{k-1})$