跟随carl代码随想录刷题
语言：python

此方法适用于N数之和的题目

15. 中等三数之和

题目：给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有和为 0 且不重复的三元组。
注意：答案中不可以包含重复的三元组。
👉示例 1：
输入：nums = [-1,0,1,2,-1,-4]
输出：[[-1,-1,2],[-1,0,1]]
👉示例 2：
输入：nums = []
输出：[]
👉示例 3：
输入：nums = [0]
输出：[]

题目分析

😭坑好多！

1. ⭐️对数组进行排序
2. 定义三个指针i、left、right
3. 如果nums[i] > 0，说明该数组最小值都大于0，则不存在等于0的三元组，结束循环break
4. 如果nums[i] == nums[i-1]，说明当前值和已经遍历过的存在重复，可以跳过，continue。对i 去重
5. 移动left和right查找满足要求的三元组。注意，遍历要始终满足left < right ：
   a. 如果三元组之和大于0，则right -= 1
   b. 如果三元组之和小于0，则left += 1
   c. 如果三元组之和等于0，则将nums[i], nums[left], nums[right]保存到结果集中
   • 对left去重如果nums[left] == nums[left + 1]，则left += 1
   • 对right去重如果nums[right] == nums[right + 1]，则right += 1

完整代码如下

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        n = len(nums)
        nums.sort()
        result = []
        
        # 对数组进行排序
        for i in range(n-2):
            left = i+1
            right = n-1

            if nums[i]>0:
                break

            if i>0 and nums[i] == nums[i-1]:
                continue
            
            while left < right:
                total = nums[i] + nums[left] + nums[right]
                if total > 0:
                    right -= 1
                elif total < 0:
                    left += 1
                
                else:
                    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
        return result
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
29
30
31

sort、sorted

python数组排序方法详解（sort， sorted，argsort）

18. 中等四数之和

题目：给你一个由 n 个整数组成的数组 nums ，和一个目标值 target 。请你找出并返回满足下述全部条件且不重复的四元组 [nums[a], nums[b], nums[c], nums[d]] （若两个四元组元素一一对应，则认为两个四元组重复）：
0 <= a, b, c, d < n
a、b、c 和 d 互不相同
nums[a] + nums[b] + nums[c] + nums[d] == target
你可以按 任意顺序 返回答案 。
👉示例 1：
输入：nums = [1,0,-1,0,-2,2], target = 0
输出：[[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]
👉示例 2：
输入：nums = [2,2,2,2,2], target = 8
输出：[[2,2,2,2]]

原理与三数之和相同，只用多设置一个指针，同时修改一下判断条件>target、、=target

class Solution:
    def fourSum(self, nums: List[int], target: int) -> List[List[int]]:
        result = []
        nums.sort()  # 对列表排序
        n = len(nums)

        for i in range(n-3):
            if i>0 and nums[i]==nums[i-1]:
                continue
            for j in range(i+1,n-2):  # 多设置一个指针
                if j>i+1 and nums[j]==nums[j-1]:
                    continue
                    
                left = j + 1
                right = n - 1

                while left<right:
                    total = nums[i] + nums[j] + nums[left] + nums[right]
                    if total < target:
                        left += 1
                    elif total > target:
                        right -= 1
                    else:
                        result.append([nums[i], nums[j], 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 result
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
29