四数之和

# -*- coding: utf-8 -*-

# coding:utf-8
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
#
# @param nums int整型一维数组
# @param target int整型
# @return int整型二维数组
#
class Solution:
    """
    题目：
        https://www.nowcoder.com/practice/d5b74806fa104518903884e182f47e35?tpId=196&tqId=40414&rp=1&ru=/exam/oj&qru=/exam/oj&sourceUrl=%2Fexam%2Foj%3Fpage%3D7%26tab%3D%25E7%25AE%2597%25E6%25B3%2595%25E7%25AF%2587%26topicId%3D196&difficulty=undefined&judgeStatus=undefined&tags=&title=
    算法：
        题目要求获取nums[a] + nums[b] + nums[c] + nums[d] = target的所有不同组合[nums[a], nums[b], nums[c], nums[d]]
        枚举nums[a]: # a的取值范围[a: n-3)
            对a去重
            枚举nums[b]：# b的范围[a+1: n-2)
                对b去重
                双指针c和d，在区间[b+1:n)中，寻找满足条件的组合，同时对c, d分别去重
    复杂度：
        时间复杂度：O(N^3)，N为数组nums的长度
        空间复杂度：O(N)，排序算法所需的空间复杂度
    """

    def fournumber(self, nums, target):
        # write code here
        n = len(nums)

        nums.sort()

        res = []
        for a in range(n - 3):
            if a > 0 and nums[a] == nums[a - 1]: # 对a去重，剪枝
                continue
            for b in range(a + 1, n - 2):
                if b > a + 1 and nums[b] == nums[b - 1]: # 对b去重，剪枝
                    continue
                c, d = b + 1, n - 1
                while c < d:
                    Sum = nums[a] + nums[b] + nums[c] + nums[d]
                    if Sum == target:
                        res.append([nums[a], nums[b], nums[c], nums[d]])
                        while c < d and nums[c] == nums[c + 1]: # 对c去重，剪枝
                            c += 1
                        while c < d and nums[d] == nums[d - 1]: # 对d去重，剪枝
                            d -= 1
                        c += 1
                        d -= 1
                    elif Sum > target:
                        d -= 1
                    else:
                        c += 1
        return res


if __name__ == "__main__":
    sol = Solution()

    # nums, target = [2, 0, -2, 3, -3, 0], 0

    # nums, target = [2, 0, -2, 0, 1, -3, 4, -4], -4

    nums, target = [3, 2, 4, -3, -5, -3, -2, 2, 0, 4, -3], 1

    res = sol.fournumber(nums, target)

    print res