题目来源LeetCode 15.三数之和
本贴为个人日常刷题笔记，有任何问题欢迎随时交流~
该题类别是：数组

一、题目

  • 给你一个包含 n 个整数的数组nums，判断nums中是否存在三个元素 a，b，c ，使得a + b + c = 0？请你找出所有和为 0 且不重复的三元组。

  • 注意：答案中不可以包含重复的三元组。

二、提示

  • 0 ≤ n u m s . l e n g t h ≤ 3000 0 \le nums.length \le 3000 0≤nums.length≤3000
  • − 1 0 5 ≤ n u m s [ i ] ≤ 1 0 5 -10^5 \le nums[i] \le 10^5 −105≤nums[i]≤105

三、思考

题限思考

  • nums长度范围
  • nums元素的取值范围
  • 返回三元组，注意nums的边界，如果是len(nums)小于等于2，直接返回空列表
  • nums是否有序，题目给定是无序的
  • 不重复，去重

解法思考

  • 边界判定，len(nums) <= 2，直接返回

  • 先将nums排序

  • 特殊点，若最左边的数比target=0大，或最右边的数比target=0小，直接输出空列表

  • 设定三个指针，最外层循环固定一指针i，从0开始遍历

  • 左指针i指向0位置，中间指针j从i+1开始，右指针k从j+1开始

  • 暴力解法

    • i从0到len(nums) - 2的位置停止
    • j从i+1到len(nums) - 1的位置停止
    • k从j+1到len(nums) 的位置停止
    • 这种思路下，当 l e n ( n u m s ) ≤ 2 len(nums) \le 2 len(nums)≤2时，显然k停止可以直接返回值，即包含边界
    • 注意：不可重复意味着需要值比较
      • 移动时判断是否与前一个值相同，是则跳过

  • 优化思路（内嵌双指针）

    • i从0到len(nums) - 2的位置停止
    • j从i+1开始
    • k从len(nums) - 1开始
    • 如果在nums[i]不变的情况下，while j < k
      • 若nums[i] + nums[j] + nums[k] < target，j += 1
      • 若nums[i] + nums[j] + nums[k] > target， k -= 1
    • 注意边界是否包含
    • 如何去重

四、解法（双指针）

  • 从小案例入手：

    nums = [4, 1, 7, -6, 1, 5]

    target = 0

    sort_nums = [-6, 1, 1, 4, 5, 7]

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

  • 代码实现

     class Solution:
     def threeSum(self, nums: List[int]) -> List[List[int]]:
         res = list()
         nums.sort()
         for i in range(0, len(nums) - 2):
             if nums[i] > 0:		# 这一层是对于特殊0而言的用法
                 break
             if i > 0 and nums[i] == nums[i - 1]:
                 continue
             mid = i + 1
             j = len(nums) - 1
             while mid < j:
                 temp = nums[i] + nums[mid] + nums[j]
                 if temp < 0:
                     mid += 1
                     # 这里不需要去重
                     # while j < k and nums[j] == nums[j-1]: 
                        # j += 1
                 elif temp > 0:
                     j -= 1
                 else:
                     res.append([nums[i], nums[mid], nums[j]])
                     while mid < j and nums[mid] == nums[mid + 1]:
                         mid += 1
                     while mid < j and nums[j] == nums[j - 1]:
                         j -= 1
                     mid += 1
                     j -= 1
         return res