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、rightleft = 0right = len(new_sum) - 1while 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 += 1else:right -= 1# 将 return None 移到循环外面return None

4、新知识点

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 null

3）如何不打乱索引，进行排序

始终，这种方式改变了原始数组的顺序。若原始数组的顺序不变，可以使用哈希表方法。

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 40

6）列表推导式

列表推导式是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 = 0right = len(nums)-1res =[]while left < right:current_sum = nums[left] + nums[right]# 如果和等于目标值 target：if current_sum == target :pair =[nums[left],nums[right]]#要返回多个,存到一个列表里res.append(pair)left +=1right -=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 +=1while nums[left] < nums[right] and nums[right] == nums[right-1]:right -= 1elif current_sum < target :left += 1else:right -=1return 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 + 1k = n - 1while 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 += 1while j < k and nums[k] == nums[k-1]:k -= 1j += 1k -= 1elif curr_sum < 0:j += 1else:k -= 1return resAI版：
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]:  # 跳过重复元素continuej, k = i + 1, n - 1while 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 += 1while j < k and nums[k] == nums[k - 1]:k -= 1j += 1k -= 1elif curr_sum < 0:j += 1else:k -= 1return 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]:continuefor j in range(i + 1,n):if j > i + 1 and nums[j] == nums[j - 1]:continueleft = j + 1right = n - 1while 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 += 1while left < right and nums[right] == nums[right - 1]:right -= 1left += 1right -= 1elif cur_sum > target:right -= 1else:left += 1return resif __name__ =='__main__':nums =[1,0,-1,0,-2,2]target = 0solution = 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]:continuefor j in range(i + 1, n - 2):if j > i + 1 and nums[j] == nums[j - 1]:continuecomplement = 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) + 1return res