Leetcode Two pointers 18,209 @Python－CONY的世界

18. 4Sum

Given an array S of n integers, are there elements a, b, c, and d in S such that a + b + c + d = target? Find all unique quadruplets in the array which gives the sum of target.

Note: The solution set must not contain duplicate quadruplets.

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]
]

Success:

我一開始想到的方法比較慢，先固定two sum 然後再用left, right 找到剩餘符合 target value 的值

當然two sum 還是要考慮到不能重複，所以才會在for loop 一開始有個醜醜的判斷式來決定到底要不要做

1008 ms, beats 36.12 % of python submissions

class Solution(object):
    def fourSum(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[List[int]]
        """
        res = []
        if len(nums) < 4:
            return res
        nums.sort()
        for index1 in range(len(nums)):
            if index1 > 0 and nums[index1] == nums[index1-1]:
                    continue
            for index2 in range(index1+1, len(nums)):
                if index2 > index1+1 and nums[index2] == nums[index2-1]:
                    continue
                twosum = nums[index1]+nums[index2]
                left, right = index2 + 1, len(nums)-1
              #  print "%d (%d) %d(%d) %d(%d) %d(%d)" % (index1, nums[index1], index2,nums[index2], left,nums[left],right,nums[right])
                while left < right:
                    s = nums[left] + nums[right] + twosum - target
                    if s > 0:
                        right -= 1
                    elif s < 0:
                        left += 1
                    else:
                        res.append([nums[index1], nums[index2], nums[left], nums[right]])
                       # print "append [%d,%d,%d,%d]" % (nums[index1], nums[index2], nums[left], nums[right])
                        while left < right and nums[left] == nums[left+1]:
                            left += 1
                        while left < right and nums[right] == nums[right-1]:
                            right -= 1
                        left += 1
                        right -= 1
        return res

官版如同之前3 sum c++解法，這次找到python版的，一樣是先實作 k sum ，然後 k ＝ 4

class Solution(object):
    def fourSum(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[List[int]]
        """
        def Ksum(nums, target, N, result, results):
            if (len(nums) < N) or (N < 2) or (nums[0]*N > target) or (nums[-1]*N < target):
                return
            if N == 2:
                l, r = 0, len(nums)-1
                while l < r:
                    s = nums[l] + nums[r] - target
                    if s > 0:
                        r -= 1
                    elif s < 0:
                        l += 1
                    else:
                        results.append(result + [nums[l], nums[r]])
                        l += 1
                        while l < r and nums[l] == nums[l-1]:
                            l += 1
            else:
                for i in range(len(nums)-N+1):
                    if i == 0 or (i > 0 and nums[i] != nums[i-1]):
                        Ksum(nums[i+1:], target-nums[i], N-1, result+[nums[i]], results)
        res = []
        Ksum(sorted(nums), target, 4, [], res)
        return res

主要實作重點是
1. K sum 的 nums 要扣掉固定的那個
2. results 是 result + nums[l] +nums[r]
3.  s= 0 加完 list 後，其實 r 和 l 只要移動一邊就好了
4.  可以把sorted(nums) 放在 Ksum 參數裡面，這樣更簡潔

209. Minimum Size Subarray Sum

Given an array of n positive integers and a positive integer s, find the minimal length of a contiguous subarray of which the sum ≥ s. If there isn't one, return 0 instead.

For example, given the array [2,3,1,2,4,3] and s = 7,
the subarray [4,3] has the minimal length under the problem constraint.

Success:

想用dic 做結果就time exceed，只好參考官方做法

其實做法蠻簡單的，考慮到要連續，所以用兩個頭尾 pointer 掃過就好

class Solution(object):
    def minSubArrayLen(self, s, nums):
        """
        :type s: int
        :type nums: List[int]
        :rtype: int
        """
        total = left = 0
        result = len(nums) + 1
        for right, n in enumerate(nums):
            total += n
            while total >= s:
                result = min(result, right - left + 1)
                total -= nums[left]
                left += 1
        return result if result <= len(nums) else 0

Fail:

class Solution(object):
    def minSubArrayLen(self, s, nums):
        """
        :type s: int
        :type nums: List[int]
        :rtype: int
        """
        table={}
        if len(nums) == 0 or (len(nums) == 1 and nums[0] != s):
            return 0
        for length in range(0,len(nums)+1):
            for start in range(len(nums)-length):
                result = 0
                if table.has_key((start,start+length-1)):
                    result = table[(start,start+length-1)] + nums[start+length]
                else:
                    for index in range(start, start+length+1):
                        result += nums[index]
                if result >= s:
                    return length+1
                table[(start,start+length)] = result
                #print "[%d,%d] %d,"% (start, start+length, result)
        return 0