Leetcode 15&16

|
| 字数统计: 646

15. 3Sum

Given an array nums of n integers, are there elements a, b, c in nums such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero.

##Note:

The solution set must not contain duplicate triplets.

##Example:

Given array nums = [-1, 0, 1, 2, -1, -4],

A solution set is:
[
[-1, 0, 1],
[-1, -1, 2]
]
用集合做

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
from collections import Counter
class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        counter=Counter(nums)
        numset=set(nums)
        numlist=sorted(list(numset))
        print(numlist)
        res=[]
        if 0 in counter:
            if counter[0]>=3:
                res.append([0,0,0])
        for i in range(len(numlist)):
            for j in range(i+1,len(numlist)):
                sum=-numlist[i]-numlist[j]
                if sum in numset:
                    if sum!=numlist[i] and  sum!=numlist[j] and numlist.index(sum)<j:
                        continue
                    if sum==numlist[i]:
                        if counter[numlist[i]]>=2:
                            res.append([numlist[i],numlist[i],numlist[j]])
                        continue
                    if sum==numlist[j]:
                        if counter[numlist[j]]>=2:
                            res.append([numlist[i],numlist[j],numlist[j]])
                        continue
                    res.append([numlist[i],numlist[j],sum])
        return res

另外一种方法是用左右移动调整的方法
If we sort the the list, then we can consider each number in the list as b in equation a+b+c=0, and to find a and c, we can start from the two edges of the list and move towards center.

For example in nums=[-3, -2, 0, 1, 4, 6] if we have chosen nums[3]=1 as the center, then at first left=nums[0]=-3 and right=nums[5]=6. If a+b+c = 0, then we add [a,b,c] to ans, only if it was not there already; and we move both left and right towards the center to consider new values for a and c.

If the sum of the three numbers is greater than 0, then we need to move the right one step towards the center to get a smaller sum; and if the sum is less than 0, we need to move the left towards center to get a larger sum value.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        ans = set()
        nums.sort()
        
        for center in range(len(nums)-1):
            left = 0
            right = len(nums)-1
            
            while left < center and center < right:
                
                temp = nums[left] + nums[center] + nums[right]
                
                if temp == 0:
                    if (nums[left], nums[center], nums[right]) not in ans:
                        ans.add((nums[left], nums[center], nums[right]))
                    left += 1
                    right -= 1
                elif temp > 0:
                    right -= 1
                elif temp < 0:
                    left += 1
        return list(ans)

类题如下

16. 3Sum Closest

Given an array nums of n integers and an integer target, find three integers in nums such that the sum is closest to target. Return the sum of the three integers. You may assume that each input would have exactly one solution.

##Example:

Given array nums = [-1, 2, 1, -4], and target = 1.

The sum that is closest to the target is 2. (-1 + 2 + 1 = 2).
同理

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution:
    def threeSumClosest(self, nums: List[int], target: int) -> int:
        sort_nums=sorted(nums)
        best=math.inf
        for center in range(1,len(sort_nums)-1):
            left=0
            right=len(sort_nums)-1
            while left<center and center<right:
                temp = sort_nums[left]+sort_nums[center]+sort_nums[right]
                if abs(temp-target)<abs(best-target):
                    best=temp
                if temp==target:
                    return target
                elif temp>target:
                    right-=1
                elif temp<target:
                    left+=1
        return best