Leetcode 18

Posted on | | 阅读数
Words count in article: 443 | Reading time ≈ 2

Question

Solution1

首先对nums进行排序。[x,y,z,h,i,j,k]然后考虑先去前两个数，添加两个指针，第一个指向z，第二个指向末位元素，即k。计算target-x-y，将其与z+k进行比较，如果相同则是一个结果，如果z+k小，则第一个指针右移动一个位置，如果大，则第二个指针左移一个位置。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution:
    def fourSum(self, nums: List[int], target: int) -> List[List[int]]:
        results = set()
        n = len(nums)
        nums = sorted(nums)
        for i in range(n-3):
            for j in range(i+1, n-2):
                residual = target - nums[i] - nums[j]
                left = j + 1
                right = n - 1
                while left < right:
                    if nums[left] + nums[right] == residual:
                        results.add(tuple([nums[i], nums[j], nums[left], nums[right]]))
                        left += 1
                    elif nums[left] + nums[right] < residual:
                        left += 1
                    else:
                        right -= 1
        return sorted([list(x) for x in results])

Solution2

适用更广的答案。N可以是任意数目。

当N大于2时，采用dfs来迭代。当N==2时，采用两个指针的方法，一头一尾，不断的进行比较。需要注意的是避免重复情况。dfs里面的条件判断就是为了避免重复情况。同时在N==2里面，有一个while循环，也会是为了避免重复情况。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution:
    def fourSum(self, nums: List[int], target: int) -> List[List[int]]:
        results = []
        self.dfs(sorted(nums), target, [], results, 4)
        return results
    
    def dfs(self, nums, target, temp, results, N):
        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]
                if s == target:
                    results.append(temp+[nums[l], nums[r]])
                    l += 1
                    while l < r and nums[l] == nums[l-1]:
                        l += 1
                elif s < target:
                    l += 1
                else:
                    r -= 1
        
        else:
            for i in range(len(nums)-N+1):
                if i == 0 or (i > 0 and nums[i] != nums[i-1]):
                    self.dfs(nums[i+1:], target-nums[i], temp+[nums[i]], results, N-1)