python求数组的所有组合：Python数组中求和问题
python求数组的所有组合：Python数组中求和问题（2） 考虑暴力循环中我们做的事情，我们先挑出一个值a，然后看数组中其他值是否能与值a相加等于目标，也可以说成看数组中是否存在一个值等于目标值减去值a。（1） O（n） 因为 nums[0] nums[1] = 2 7 = 9 所以返回 [0 1]O(n^2)唯一需要注意的是同一个元素不能复用
优效学院，大数据，java，人工智能，架构，等在线教育本专题主要介绍哈希表和指针两种方法来解决该类问题，从两个数之和引申到三个数之和，再从四个数之和的问题上思考如何构建出一种通用的代码（可以解决N个数之和）。本文主要内容是通过001问题来初步了解数组求和的两种常用方法。
001-Two Sum给定一个整数数组和一个目标值，找出数组中和为目标值的两个数。 你可以假设每个输入只对应一种答案，且同样的元素不能被重复利用。
示例 :
给定 nums = [2 7 11 15] target = 9
因为 nums[0] nums[1] = 2 7 = 9 所以返回 [0 1]
1. 暴力循环O(n^2)
唯一需要注意的是同一个元素不能复用
（1） O（n）
（2） 考虑暴力循环中我们做的事情，我们先挑出一个值a，然后看数组中其他值是否能与值a相加等于目标，也可以说成看数组中是否存在一个值等于目标值减去值a。
（3） 换个思路，我们将所有遍历过的值存放起来，每次遍历到一个新的值b时，我们可以查找目标值减去值b是否在我们存放的值中。基于哈希表的特性，查找的时间复杂度为O（1），总时间复杂度就变为了一次for循环O（n）
回到本道题中:
（1） 由于需要返回对应的索引，所以需要使用HashMap（在Python中是dict），key存放数组中的值，value存放数组中的索引，遍历数组，将遍历过的值存入dict，如果目标值减去当前值在dict中则证明找到了目标值。
（2） 还有一点需要注意的是如果想按从小到大的顺序返回值，dict中存放的肯定是前一个值（因为是之前遍历过的）。
（1） O(nlogn)-主要是快排的影响
（2） 在一个有序的数组中最左边一定是最小值，而最右边一定是最大值。我们可以将最小值与最大值相加与目标值进行比较，如果两数之和大于目标值，我们就让最大值小一点（也就是读取第二个最大值），相反如果小于，则让最小值大一点（读取第二个最小值）。这样我们就保证了一次循环就能查找到目标值，但数组必须是有序的。
回到题目中:
（1） 由于需要返回索引，所以我们必须存储两个数组，一个是无序的（用于查找真实的索引），另一个是有序的（用于查找符合题目的值）。
（2） 两个指针left和right分别指向数组中第一个元素和最后一个元素（最小值和最大值）
（3） 循环的结束条件为左指针大于等于右指针（左边的不能比右边的大，而且一个元素只能用一次）
（4） 然后就判断左值 右值与目标值之间的关系，在上面我们已经讨论过了大于和小于的情况。
（5） 当等于时由于我们需要得到左值和右值在原本数组的索引，我们需要考虑以下问题。从题目中的得知每个target只有一个答案 意味着如果target是6不会出现[2 2 4]的情况 但是会出现[3 3]的情况 也就是当两个相同的值满足情况是才会有重复的元素。所以我们先通过index获取左值对应的索引，如果左值和右值相同我们就获取下一个该值的索引，如果不同，我们直接获取右值相关的索引。
总结
通过两个数求和问题初步了解数组求和问题，下一文将引申这两种方法在三个数求和中的应用。
Python资料的私聊小编
