{"id":71,"date":"2019-03-29T05:21:59","date_gmt":"2019-03-28T21:21:59","guid":{"rendered":"http:\/\/washingpatrick.cn\/?p=71"},"modified":"2019-04-09T10:13:04","modified_gmt":"2019-04-09T02:13:04","slug":"n-number-solution","status":"publish","type":"post","link":"https:\/\/washingpatrick.cn\/index.php\/2019\/03\/29\/n-number-solution\/","title":{"rendered":"N-number Solution"},"content":{"rendered":"<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"python\">class Solution:\r\n    def fourSum(self, nums: List[int], target: int) -&gt; List[List[int]]:\r\n        def findNsum(nums, target, N, result, results):\r\n            if len(nums) &lt; N or N &lt; 2 or target &lt; nums[0]*N or target &gt; nums[-1]*N:  # early termination\r\n                return\r\n            if N == 2: # two pointers solve sorted 2-sum problem\r\n                l,r = 0,len(nums)-1\r\n                while l &lt; r:\r\n                    s = nums[l] + nums[r]\r\n                    if s == target:\r\n                        results.append(result + [nums[l], nums[r]])\r\n                        l += 1\r\n                        while l &lt; r and nums[l] == nums[l-1]:\r\n                            l += 1\r\n                    elif s &lt; target:\r\n                        l += 1\r\n                    else:\r\n                        r -= 1\r\n            else: # recursively reduce N\r\n                for i in range(len(nums)-N+1):\r\n                    if i == 0 or (i &gt; 0 and nums[i-1] != nums[i]):\r\n                        findNsum(nums[i+1:], target-nums[i], N-1, result+[nums[i]], results)\r\n    results = []\r\n    findNsum(sorted(nums), target, 4, [], results)\r\n    return results<\/pre>\n<p>&nbsp;<\/p>\n","protected":false},"excerpt":{"rendered":"<p>class Solution: def fourSum(self, nums: List[int], targ&#8230; <\/p>\n<div class=\"read-more navbutton\"><a href=\"https:\/\/washingpatrick.cn\/index.php\/2019\/03\/29\/n-number-solution\/\">\u9605\u8bfb\u66f4\u591a<i class=\"fa fa-angle-double-right\"><\/i><\/a><\/div>\n","protected":false},"author":1,"featured_media":0,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[1],"tags":[],"class_list":["post-71","post","type-post","status-publish","format-standard","hentry","category-uncategorized"],"_links":{"self":[{"href":"https:\/\/washingpatrick.cn\/index.php\/wp-json\/wp\/v2\/posts\/71","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/washingpatrick.cn\/index.php\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/washingpatrick.cn\/index.php\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/washingpatrick.cn\/index.php\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/washingpatrick.cn\/index.php\/wp-json\/wp\/v2\/comments?post=71"}],"version-history":[{"count":3,"href":"https:\/\/washingpatrick.cn\/index.php\/wp-json\/wp\/v2\/posts\/71\/revisions"}],"predecessor-version":[{"id":75,"href":"https:\/\/washingpatrick.cn\/index.php\/wp-json\/wp\/v2\/posts\/71\/revisions\/75"}],"wp:attachment":[{"href":"https:\/\/washingpatrick.cn\/index.php\/wp-json\/wp\/v2\/media?parent=71"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/washingpatrick.cn\/index.php\/wp-json\/wp\/v2\/categories?post=71"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/washingpatrick.cn\/index.php\/wp-json\/wp\/v2\/tags?post=71"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}