2sum问题
初级：返回一对数字的索引
给定一个整数型数组nums，再给定一个整数型目标值target,假定数组nums中，
有且仅有一对元素之和，为target,
找出这2个元素，输出他们的索引，元素在答案中不可重复出现。一、方法1：双指针技巧 -- (先排序，再双指针)
1、步骤1、列表排序
如果不是非要返回索引，就更简单，直接对原始列表排序即可。
1）保留原始列表nums的索引值，需要新创建一个列表new_sum
根据enumerate（）函数，建立原始数组的索引和元素值的映射
使用列表推导式，创建新的列表new_sum
2）对新列表，进行排序
使用sort（）函数，对根据新列表里元素的值，进行从小到大排序
2、步骤2、左右双指针技巧，从两端相向而行
【keypoint】: 要用新列表的方式，来表示原始数组的索引
指针A、B是新列表的指针。
new_sum[A]，表示新列表的一个元素（本质是原始列表元素值和索引构成的一个元组）
若元组的组成是：（索引，元组值），则原始索引new_sum[A][0] ，值是new_sum[A][1]
若元组的组成是：（元组值，索引），则原始索引new_sum[A][1] ，值是new_sum[A][0]
1）新列表指针A在索引0，指针B在 索引 len(new_sum) -1 的位置，从两端相向而行
2）当A小于B时，new_sum[A][1] + new_sum[B][1] = target
(要用int值与int值相比，不能拿元组和int值相比)
3）当A = B时，不需要考虑，因为结果中，A 和 B 不能是重复的元素
4）当A> B，也不需要考虑，因为 这种情况和 B>A 遍历起来是一样的结果
思路遗漏的细节：
1、指针是如何运动的
2、应该使用什么语法3、解法：
class Solution:
def twoSum(self, nums: list[int], target: int) -> list[int]:
# 先对数组进行排序：
# 1）先创建一个新列表。这个列表推导式的新列表的元素构造是由enumerate()完成的
new_sum = [(i, num) for i, num in enumerate(nums)]
# 2）对新列表进行排序,根据元素值，进行排序
new_sum.sort(key=lambda x: x[1])
# 初始化两个左右指针left、right
left = 0
right = len(new_sum) - 1
while left < right:
current_sum = new_sum[left][1] + new_sum[right][1]
if current_sum == target:
# 返回原始索引
return [new_sum[left][0], new_sum[right][0]]
elif current_sum < target:
left += 1
else:
right -= 1
# 将 return None 移到循环外面
return None4、新知识点
1）返回元素，还是索引的区别
1、看清题目，是返回元素，还是返回元素的索引
如果是返回元素，就可以对数组，进行排序，使用sort(),默认从小到大排序
如果是返回元素的索引，就不能对数组进行排序，会打乱索引的值2）不同类型的返回值，返回空的写法
2、如果就不存在符合条件的值，那么就要根据返回类型，返回空
1）如果要返回的是列表，那么返回空，应该写为 return []
2) 如果要返回的是元组，那么返回空，应该写为 return ()
3）如果要返回的是字符串，那么返回空，应该写为 return ""
4）如果要返回的是字典，那么返回空，应该写为 return {}
5）如果要返回的是空集合，那么返回空，应该写为 return set()
6）如果要返回的是数值，那么返回空，可以写为特殊数字或者None: return -1、0、None ,
7)在面向对象编程中，当函数的返回值是一个对象，但没有实际的对象实例时，返回空对象
python中返回空，应该写为 return None
Java中返回空，应该写为 return null3）如何不打乱索引，进行排序
始终，这种方式改变了原始数组的顺序。若原始数组的顺序不变，可以使用哈希表方法。
1、使用enumerate（）和列表推导式，创建一个新列表，其中每个元素都是个元组。
2、使用sort（）排序方法，根据每个元组中，元素值的大小进行排序
一、创建 元素 和 索引的映射关系--创建一个新列表
1）现存在数组nums，为list[int]类型
2) 创建映射--新列表indexed：
indexed = [(i, num) for i, num in enumerate(nums)]
解释：
创建一个新列表indexed，其中每个元素是一个元组(i, num)，num是数组nums中的值，i是该值在原始数组中的索引。
实现：使用列表推导式和enumerate函数。enumerate(nums)会生成一个包含索引和值的元组序列，
例如[(0, nums[0]), (1, nums[1]), ...]。列表推导式将这些元组转换为(i, num)的形式。
二、对新列表的元素值，进行排序
indexed.sort(key=lambda x: x[1])
目标：对indexed_nums列表按数值num进行排序
实现：
使用sort方法和lambda函数。
key=lambda x: x[0] 表示排序的依据是元组的第1个元素（即数值i）。
key=lambda x: x[1] 表示排序的依据是元组的第2个元素（即数值num）。
排序后，indexed中的元组按数值num从小到大排列。
4）sort（）函数的使用
1. sort方法
sort是Python列表（list）的一个内置方法，用于对列表中的元素进行排序。
它会原地修改列表，即直接在原列表上进行排序，不会返回一个新的列表。
2. key参数
sort方法有一个可选参数key，它是一个函数，用于从列表中每个元素中提取一个用于排序的键（key）。
3. lambda函数
lambda是一个匿名函数，用于创建简单的函数对象。
它的语法是lambda arguments: expression，可以接受任意数量的参数，但只能有一个表达式。
lambda x: x[0]：
这是一个匿名函数，
接受一个参数x（列表中的一个元组），
并返回元组的第一个元素x[0]（即数值num）
key=lambda x: x[0]：
将这个匿名函数作为key参数传递给sort方法。
sort方法会使用这个函数来提取每个元组的数值num，并根据这些数值进行排序。
一、sort(key=lambda x: x[0]) 的具体使用
indexed_nums = [(3, 0), (1, 1), (4, 2), (2, 3)]
1、indexed_nums.sort(key=lambda x: x[0])
print(indexed_nums)
执行上述代码后，indexed_nums将被排序为：
[(1, 1), (2, 3), (3, 0), (4, 2)]
2、indexed_nums.sort(key=lambda x: x[1])
执行上述代码后，indexed_nums将被排序为：
[(3, 0), (1, 1), (4, 2), (2, 3)]
5）enumerate（）
enumerate（）可以对一个可迭代的对象（如：列表、元组、字符串）组合成一组索引序列。
同时展示 元素值和其索引
用法：enumerate(nums，start)，如果 start不写，默认是从索引0开始。
例如：
nums = [10, 20, 30, 40]
使用enumerate(nums)：
for i, num in enumerate(nums):
print(i, num)
执行上述代码后，输出结果为：
0 10
1 20
2 30
3 406）列表推导式
列表推导式是Python中简洁构建列表的方法。列表推导式可以快速生成一个新列表。
它的语法形式为：[expression for item in iterable]
结合enumerate和列表推导式
indexed_nums = [(num, i) for i, num in enumerate(nums)]
print(indexed_nums)
新列表结果为：
[(10, 0), (20, 1), (30, 2), (40, 3)]
二、方法2：for循环穷举
步骤1、
步骤2：
解法
中级：返回所有满足条件的元素对
nums 中可能有多对儿元素之和都等于 target，请你的算法返回所有和为 target 的元素对儿，
其中不能出现重复。
比如说输入为 nums = [1,3,1,2,2,3], target = 4，那么算法返回的结果就是：[[1,3],[2,2]]（注意，我要求返回元素，而不是索引）。
对于修改后的问题，关键难点是现在可能有多个和为 target 的数对儿，
还不能重复，比如上述例子中 [1,3] 和 [3,1] 就算重复，只能算一次。思路：
一、方法一：排序+双指针
重点是返回所有和去重
1、步骤1：满足条件的元素要进行累加
在while循环中，对于满足条件的多个元素，要累加成一个列表，进行返回
1）累加的列表，起初，需要初始化一个空列表，res=[] :这也是一个列表推导式
2）累加的数据，需要使用res.append（）来累加到列表里面
3）累加，则为多次循环，需要指针有动作，才能循环起来：left += 1, right- =1
2、步骤2：所有符合条件的数据，要去重
1）在判断条件里面，去重
首先，left < right 的大前提是不变的，
那么何时才会出现重复呢，也就是 nums[left] + nums[right] = target时，的数据才有重复的
在这个大前提下，要判断，
1.1）nums[left] 和 nums[right] 是否相同，若相同，要跳过。
1.2) nums[left] 和 nums[right] 不同，则为nums[left] < nums[right]（因为left->right是升序的），要进而判断 left 和 right 周边是否有相同值的元素。
1.2.1）nums[left] == nums[left+1]，要跳过这种元素，left指针要适当向右移动
1.2.2）nums[right] == nums[right-1]，要跳过这种元素，right 指针要适当向左移动
解法
class Solution:
def twoSum(self, nums: list[int], target: int) -> list[int]:
nums.sort()
left = 0
right = len(nums)-1
res =[]
while left < right:
current_sum = nums[left] + nums[right]
# 如果和等于目标值 target：
if current_sum == target :
pair =[nums[left],nums[right]]
#要返回多个,存到一个列表里
res.append(pair)
left +=1
right -=1
# 检查 nums[left] 和 nums[right] 是否相同。如果相同，需要跳过重复元素。
# 如果 nums[left] 和 nums[right]不同，直接返回结果。
# 在找到匹配的元素对后，如果 nums[left] 或 nums[right] 与前一个元素相同，
# 适当地移动 left 或 right 指针。
while nums[left] < nums[right] and nums[left] == nums[left+1]:
left +=1
while nums[left] < nums[right] and nums[right] == nums[right-1]:
right -= 1
elif current_sum < target :
left += 1
else:
right -=1
return res新知识
1、range(7)
是一个在编程中常见的函数调用，尤其是在 Python 中。它的具体含义是生成一个从 0 开始到 6 结束的整数序列，不包括 7
高级-：返回三数之和
问题：
给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 0 。请你返回所有和为 0 且不重复的三元组。
注意：答案中不可以包含重复的三元组。
示例 1：
输入：nums = [-1,0,1,2,-1,-4]
输出：[[-1,-1,2],[-1,0,1]]
解释：
nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0 。
nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0 。
nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0 。
不同的三元组是 [-1,0,1] 和 [-1,-1,2] 。
注意，输出的顺序和三元组的顺序并不重要。
示例 2：
输入：nums = [0,1,1]
输出：[]
解释：唯一可能的三元组和不为 0 。
示例 3：
输入：nums = [0,0,0]
输出：[[0,0,0]]
解释：唯一可能的三元组和为 0 。解答
class Solution:
def threeSum(self, nums: list[int]) -> list[list[int]]:
nums.sort()
n = len(nums)
res = []
for i in range(n):
#自己写的，不正确
# j = 0
# k = n
#正确如下：
j = i + 1
k = n - 1
while j < k:
curr_sum = nums[i]+nums[j]+nums[k]
if curr_sum == 0:
# res.append([nums[i]+nums[j]+nums[k]])#不应该+啊
res.append([nums[i] , nums[j] ,nums[k]])
while j < k and nums[j] == nums[j+1]:
j += 1
while j < k and nums[k] == nums[k-1]:
k -= 1
j += 1
k -= 1
elif curr_sum < 0:
j += 1
else:
k -= 1
return res
AI版：
class Solution:
def threeSum(self, nums: list[int]) -> list[list[int]]:
nums.sort()
n = len(nums)
res = []
for i in range(n - 2):
if i > 0 and nums[i] == nums[i - 1]: # 跳过重复元素
continue
j, k = i + 1, n - 1
while j < k:
curr_sum = nums[i] + nums[j] + nums[k]
if curr_sum == 0:
res.append([nums[i], nums[j], nums[k]])
while j < k and nums[j] == nums[j + 1]:
j += 1
while j < k and nums[k] == nums[k - 1]:
k -= 1
j += 1
k -= 1
elif curr_sum < 0:
j += 1
else:
k -= 1
return res
if __name__ =='__main__':
nums =[-1,0,1,2,-1,-4]
solution = Solution()
result = solution.threeSum(nums)
print(result)
问题汇总
1、这行：if i > 0 and nums[i] == nums[i - 1]:，为什么是 i - 1 ，而不是 i + 1
1、避免重复使用元素：
当 i 从 0 开始递增时，i - 1 总是指向当前元素的前一个元素。通过比较 nums[i] 和 nums[i - 1]，我们可以检查当前元素是否与前一个元素相同。
如果它们相同，说明我们已经在之前的迭代中使用过这个元素来形成三元组，因此应该跳过当前迭代，
避免重复使用同一个元素。
2、逻辑正确性：
使用 i + 1 会导致比较当前元素和它后面的元素，这在逻辑上是错误的，因为我们还没有到达后面的元素。例如，当 i = 0 时，i + 1 会尝试访问 nums[1]，而我们实际上应该检查 nums[0] 和 nums[-1]（即 nums[0] 和数组的最后一个元素）。高级-四数之和
给你一个由 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
你可以按 任意顺序 返回答案 。双指针解法
class Solution:
def fourSum(self, nums: list[int], target: int) -> list[list[int]]:
nums.sort()
n = len(nums)
res = []
for i in range(n):
if i > 0 and nums[i] == nums[i - 1]:
continue
for j in range(i + 1,n):
if j > i + 1 and nums[j] == nums[j - 1]:
continue
left = j + 1
right = n - 1
while left < right:
cur_sum = nums[i] + nums[j] + nums[left] + nums[right]
if cur_sum == target:
res.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
elif cur_sum > target:
right -= 1
else:
left += 1
return res
if __name__ =='__main__':
nums =[1,0,-1,0,-2,2]
target = 0
solution = Solution()
result = solution.fourSum(nums,target)
print(result)新知识点：
1、取值范围
1）i应该是不限制取值，0~n 整个遍历
2) j为了不和i重复元素，应该从 i+1开始，到n
3) left为了不和j重复元素,应该从 j+1开始，到n
4) right为了不和j重复元素,应该从最后一个元素 n -1 开始
2、循环的取值范围
1）外层循环 (for i in range(n))：
这个循环遍历数组的第一个元素。由于我们需要四个不同的元素来形成一个四元组，所以 i 从 0 到 n-1（n 是数组 nums 的长度）。
2）第二层循环 (for j in range(i + 1, n))：
这个循环遍历数组的第二个元素。j 从 i + 1 开始，以确保 j 与 i 不同位置，即 nums[i] 和 nums[j] 是不同的元素。
3）第三层循环 (left = j + 1)：
由于 i 和 j 已经固定了两个元素，我们需要找到剩下的两个元素。left 从 j + 1 开始，确保 left 与 i 和 j 不同位置，即 nums[left] 与 nums[i] 和 nums[j] 都不同。
3、right 初始化为 n - 1 是为了确保我们从数组的最后一个元素开始寻找
哈希表法--结果不正确--得再研究：
class Solution:
def fourSum(self, nums, target):
nums.sort()
res = []
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
complement = target - nums[i] - nums[j]
lookup = {}
for k in range(j+1, n ):
w = complement - nums[k]
if w in lookup:
res.append([nums[i], nums[j], w, nums[k]])
lookup[nums[k]] =lookup.get(nums[k],0) + 1
return res