1. 两数之和

https://leetcode-cn.com/problems/two-sum/

给定一个整数数组 nums 和一个整数目标值 target，需要在数组中找到两个数，使得它们的和等于 target，并返回这两个数的数组下标。可以假设每种输入只会对应一个答案，并且不能重复使用同一个元素。可以按任意顺序返回答案。

python
展开代码
class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        hashdict=dict()
        for k,item in enumerate(nums):
            if target-item not in hashdict:
                hashdict[item]=k
            else:
                return [hashdict[target-item],k]
        
        return []

2. Two Sum II - Input Array Is Sorted (两数之和 II - 输入有序数组)

链接：https://leetcode.com/problems/two-sum-ii-input-array-is-sorted/

特点：输入数组是已排序的，且需要返回所有可能的组合（但通常题目要求返回一个组合，但可以扩展为返回所有组合）。

点评：和一般的两数之和解法一模一样，只不过这个要借助enumerate去从下标1开始，而且有空间要求。

空间复杂度 O(n) 的解法：

python
展开代码
class Solution:
    def twoSum(self, numbers: List[int], target: int) -> List[int]:
        hashdict={}
        for k,item in enumerate(numbers,1):
            if target-item not in hashdict:
                hashdict[item]=k
            else:
                return [hashdict[target-item],k]
        return []

常量级的额外空间，也就是 O(1) 的解法，使用双指针：

python
展开代码
class Solution:
    def twoSum(self, numbers: List[int], target: int) -> List[int]:
        left, right = 0, len(numbers) - 1
        while left < right:
            current_sum = numbers[left] + numbers[right]
            if current_sum == target:
                return [left + 1, right + 1]
            elif current_sum < target:
                left += 1
            else:
                right -= 1
        return [-1, -1]  # As per problem statement, this line is not needed

3. Two Sum Less Than K

给定一个整数数组 nums 和一个整数 k，返回数组中两个数的和的最大值，该和小于 k。如果没有满足条件的两个数，则返回 -1。

示例：

示例 1：输入：nums = [34,23,1,24,75,33,54,8], k = 60 输出：58 解释：34 和 24 的和是 58，且 58 小于 60，且没有其他组合的和更大。示例 2：输入：nums = [10,20,30], k = 15 输出：-1 解释：没有两个数的和小于 15。

2 三数之和

在这里插入图片描述

python

python
展开代码
from typing import List
class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        n = len(nums)
        nums.sort()
        ans = list()
        # 枚举 a
        for first in range(n):  # 遍历所有元素
            # 需要和上一次枚举的数不相同
            if first > 0 and nums[first] == nums[first - 1]:
                continue
            # c 对应的指针初始指向数组的最右端
            third = n - 1
            target = -nums[first]
            # 枚举 b
            for second in range(first + 1, n):
                # 需要和上一次枚举的数不相同
                if second > first + 1 and nums[second] == nums[second - 1]:
                    continue
                # 需要保证 b 的指针在 c 的指针的左侧
                while second < third and nums[second] + nums[third] > target:
                    third -= 1
                # 如果指针重合，随着 b 后续的增加
                # 就不会有满足 a+b+c=0 并且 b<c 的 c 了，可以退出循环
                if second == third:
                    break
                if nums[second] + nums[third] == target:
                    ans.append([nums[first], nums[second], nums[third]])
        return ans
print(Solution().threeSum([3, 5, 4, 4, -2, -2, -1, -3, -3]))

3 四数之和

https://leetcode-cn.com/problems/4sum/solution/si-shu-zhi-he-by-leetcode-solution/