1. 2sum
题目：给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。你可以假设每种输入只会对应一个答案。但是，你不能重复利用这个数组中同样的元素。
示例:
给定 nums = [2, 7, 11, 15], target = 9
因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]
思路1：不对原始数组进行排序，用一遍循环通过Hash来找出满足条件的解
代码1如下：
def twoSum(nums, target):
dicts = {}
for i in range(len(nums)):
if target-nums[i] in dicts:
return [dicts[target-nums[i]], i]
dicts[nums[i]] = i
思路2：对原数组进行排序，用首尾指针依次向中间靠拢，来找出满足条件的解。对nums=[2, 7, 11, 5]排完序后得到[2, 5, 7, 11] （相应排序前序号为[0,3,1,2]）,让左右指针从两头开始寻找，初始情况下left=0，right=3（注：这里的3是最大索引）。计算它们对应的元素之和，即2+11=13要大于target，说明元素的和需要减小，故left不变，right要变成right-1，这样就变成计算 2+7，而 2+7 刚好等于 target，所以结束循环。循环是结束了，但是并不能返回 [left,right]，因为排过序,所以应该返回排序前的索引序号，即返回 [lists[left][1], lists[right][1]]
代码2如下：
def twoSum23(nums, target):
lists = []
for i in range(len(nums)):
lists.append([nums[i], i])
lists = sorted(lists, key = lambda s:s[0])
l = 0; r = len(nums)-1
while(l<r):
if lists[l][0]+lists[r][0]==target:
return [lists[l][1], lists[r][1]]
elif lists[l][0]+lists[r][0]<target:
l+=1
else:
r-=1
2. 3sum
问题：给定一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？找出所有满足条件且不重复的三元组。
注意：答案中不可以包含重复的三元组。
例如, 给定数组 nums = [-1, 0, 1, 2, -1, -4]，
满足要求的三元组集合为：
[
[-1, 0, 1],
[-1, -1, 2]
]
思路1：遍历每个数，调用2sum算法，得到和为-num[i]的两个数
代码如下：
def Two_Sum(nums,target):
temp = []
for i in range(len(nums)-1):
for j in range(i+1,len(nums)):
if nums[i] + nums[j] == target:
temp.append([nums[i],nums[j]])
return temp
# nums =[-2,0,1,1,2]
# ret = Two_Sum(nums,target=2)
# print('ret',ret)
def threeSum(nums):
Res = {}
R = []
# nums.sort()
for i in range(0,len(nums)-2):
temp = nums[i+1:]
res = Two_Sum(temp,target = -nums[i])
if res != []:
Res[nums[i]] = [j for j in res]
# print(Res)
for key,value in Res.items():
# print(value)
for i in range(len(value)):
R.append([key,value[i][0],value[i][1]])
return max([len(i) for i in R])
R = threeSum([-2,0,1,1,2])
print('R',R)
