博主本人正在苦学算法寻找工作中，写这个系列主要是为了方便自己回看笔记和巩固知识。为了方便起见，本系列笔记不写暴力解法的相关内容，主要提炼灵茶山艾府老师视频中比较精华的讲解部分。写的不好，请见谅。

原视频链接：两数之和 三数之和【基础算法精讲 01】，博主：灵茶山艾府

一、两数之和（167. 两数之和 II - 输入有序数组）

LeetCode链接：167. 两数之和 II - 输入有序数组

思路梳理：

根据题目，我们能获取到几个关键信息：
1. 数组是非递减顺序排列的（很关键，意味着不用对其进行排序）

2. 只对应唯一的答案（意味着只要找到答案即可返回下标）

3. 最终输出的是数组的位置（也就是下标值+1）

这里用到相向双指针的方法，例如给定的数列是[2, 7, 11, 15]，target = 9，左边的指针从左向右扫描，右边的指针从右向左扫描（为了方便起见，用left代指左指针所指向的数，right代指右指针所指向的数，s代指两数之和）：
1. left = 2，right = 15，s = 17 > target，只能让右指针向左移动才能让答案值减小，来接近target的值

2. left = 2，right = 11，s = 13 > target，只能让右指针向左移动才能让答案值减小，来接近target的值

3. left = 2，right = 7，s = 9 = target，满足条件，输出结果

代码：

class Solution:
    def twoSum(self, numbers: List[int], target: int) -> List[int]:
        # 时间复杂度O(n)
        # 空间复杂度O(1)
        left = 0
        right = len(numbers) - 1
        while left < right:
            s = numbers[left] + numbers[right]
            if s == target:
                break
            if s > target:
                right -= 1
            else:
                left += 1
        return [left + 1, right + 1]

二、三数之和（15. 三数之和）

LeetCode链接：15. 三数之和

思路梳理：

我们这次可以发现这道题和上道题的细节有一些不一样：

1. 数组并非有序（意味着在一开始需要对数组进行排序，方便后面使用指针）

2. 因为排过序，所以排序后三个数字的下标i, j, k应该满足i < j < k

3. 答案中不可以包含重复的三元组（若+1之后的值与+1之前的值重复，则应该跳出循环）

本题最终应满足的值为0，即让后面两个数之和相加之和等于负的第一个数，就可以转换为第一题的思路

代码：

class Solution:
    def threeSum(self, nums: list[int]) -> list[list[int]]:
        # 时间复杂度O(n^2)
        # 空间复杂度O(1)
        nums.sort()
        # 三元组的顺序不重要
        # i < j < k
        # 答案中不可以包含重复的三元组
        ans = []
        n = len(nums)
        for i in range(n-2): # 后面要留两个数给j和k
            x = nums[i]
            if i > 0 and x == nums[i-1]: # 答案中不可以包含重复的三元组
                continue
            j = i + 1
            k = n - 1
            # 开始按照“两数之和”的方法解题
            while j < k:
                s = x + nums[j] + nums[k]
                if s > 0:
                    k -= 1
                elif s < 0:
                    j += 1
                else:
                    ans.append([x, nums[j], nums[k]])

                    j += 1
                    while j < k and nums[j] == nums[j-1]: # 要跳过重复的j值
                        j += 1
                        
                    k -= 1
                    while k > j and nums[k] == nums[k+1]: # 要跳过重复的k值
                        k -= 1
        return ans

改进代码：

class Solution:
    def threeSum(self, nums: list[int]) -> list[list[int]]:
        nums.sort()
        ans = []
        n = len(nums)
        for i in range(n-2):
            x = nums[i]
            if i > 0 and x == nums[i-1]: 
                continue

            # 改进1：如果前三个最小的数相加＞0，那么后面就没有可以满足条件的结果了
            # 因为排序后，数列是非递减的顺序排列，后面的数都比前面的大
            if x + nums[i+1] + nums[i+2] > 0:
                break    # 最小的数都不能满足，i无论怎么增大都没用

            # 改进2：如果当前数字和最大的两个数相加之和<0，那么本次循环没有满足条件的
            # 若当前能凑齐的所有最大的数字之和都没能>0，那么这次循环也不能有满足条件的数了
            if x + nums[-2] + nums[-1] < 0:
                continue    #当前不一定有，但是i值变大之后也可以满足条件

            j = i + 1
            k = n - 1

            while j < k:
                s = x + nums[j] + nums[k]
                if s > 0:
                    k -= 1
                elif s < 0:
                    j += 1
                else:
                    ans.append([x, nums[j], nums[k]])

                    j += 1
                    while j < k and nums[j] == nums[j-1]:
                        j += 1
                        
                    k -= 1
                    while k > j and nums[k] == nums[k+1]: 
                        k -= 1
        return ans