三数之和

三数之和（力扣15）

思路：为了避免重复匹配，需要先对原始数组进行排序。固定第一个数，然后对后面2个数进行筛选。这里由于排过序，可以使用双指针。特别注意的是：在双指针筛选时对重复数的判断，而且找到满足条件的组合时，left和right还需要再继续循环，而不是停止。

隔了半年再做时，还有两个点出错：

  1. 在第二个数的重复判断时
  2. 在找到满足条件的组合时不能break
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
class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        if len(nums) < 3:return[]
        nums = sorted(nums)
        result = []
        for i in range(len(nums)-2):
            if(nums[i]>0):
                return result
            if i > 0 and nums[i-1] == nums[i]:
                continue
            left, right = i+1, len(nums)-1
            while left < right:
                if nums[i] + nums[left] + nums[right] == 0:
                    result.append([nums[i],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
                elif nums[i] + nums[left] + nums[right] < 0:
                    left += 1
                else:
                    right -= 1
        return result

较小的三数之和（力扣259）

思路：这题如果采用和上题一样的思路会造成判断条件过多，仔细读题，只需要满足条件的个数，而不需要把每个都写出来，也没有重复结果的要求。所以这里在用双指针时(程序第12到14行)在获取到第一个满足条件的组合时，结果应该是right-left，然后left+=1。因为右指针的数已经满足，那么左右之间的数一定都满足，无需在移动右指针。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution:
    def threeSumSmaller(self, nums: List[int], target: int) -> int:
        if len(nums) < 3:  # 处理边界条件
            return 0
        nums.sort()
        ans = 0
        for i in range(len(nums) - 2):  # 注意i,j,k三个指针不能重合
            left = i + 1
            right = len(nums) - 1
            while left < right:
                # 如果left和right之和小于target-nums[i]，left右移
                if nums[i] + nums[left] + nums[right] < target:
                    ans += right - left
                    left += 1 
                # 如果left和right之和大于target-nums[i]，right左移
                else:
                    right -= 1
        return ans