Two Sum
Given an array of integers, return indices of the two numbers such that they add up to a specific target.
You may assume that each input would have exactly one solution, and you may not use the same element twice. [#1]
Example: Given nums = [2, 7, 11, 15], target = 9, Because nums[0] + nums[1] = 2 + 7 = 9, return [0, 1]
题意：在给定整数数组中找出2数之和等于目标值的元素下标。（假定每个输入都正好有一定答案，还有数组中每个元素只能用一次）
方法一：用现成的库函数 combinations() 在数组中任取2个数相加与目标值对比
>>> from itertools import combinations as comb >>> nums=[2,7,11,15]; target=9 >>> [[nums.index(i[0]),nums.index(i[1])] for i in comb(nums,2) if sum(i)==target][0] [0, 1] >>>
方法二：用enumerate()函数遍历数组
>>> def Sum2(nums, target): for i,n in enumerate(nums): m = target - n t = nums[i+1:] if m in t: return [i,i+1+t.index(m)] else: return [None,None] >>> nums = [2, 7, 11, 15] >>> Sum2(nums,9) [0, 1] >>> Sum2(nums,17) [0, 3] >>> Sum2(nums,22) [1, 3] >>> Sum2(nums,26) [2, 3] >>> Sum2(nums,30) [None, None] >>>
方法三：把数和对应索引号存入临时字典
>>> def Sum2(nums, target): t = {} for i,n in enumerate(nums): if target-n in t: return [t[target-n], i] else: t[n] = i >>> Sum2([2, 7, 11, 15], 22) [1, 3] >>> Sum2([2, 7, 11, 15], 9) [0, 1] >>>
Two Sum II - Input array is sorted
Given an array of integers that is already sorted in ascending order, find two numbers such that they add up to a specific target number.
The function twoSum should return indices of the two numbers such that they add up to the target, where index1 must be less than index2. [#167]
Note:
Your returned answers (both index1 and index2) are not zero-based.
You may assume that each input would have exactly one solution and you may not use the same element twice.
Example: Input: numbers = [2,7,11,15], target = 9 Output: [1,2] Explanation: The sum of 2 and 7 is 9. Therefore index1 = 1, index2 = 2.
题意：与上题基本相同，只是返回值要求是序号，不是以0开始的索引号。
>>> def Sum2(nums, target): for i,n in enumerate(nums): m = target - n t = nums[i+1:] if m in t: return [i+1,i+2+t.index(m)] else: return [None,None]
3Sum
Given an array nums of n integers, are there elements a, b, c in nums such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero. [#15]
Note:
The solution set must not contain duplicate triplets.
Example: Given array nums = [-1, 0, 1, 2, -1, -4], A solution set is: [ [-1, 0, 1], [-1, -1, 2] ]
题意：在给定整数数组中取出合计为0的三个数，结果不能有重复的三元组(duplicate triplets)。
方法一：还用组合函数比较省事，但进一步进行去重操作
>>> from itertools import combinations as comb >>> nums = [-1, 0, 1, 2, -1, -4] >>> [sorted(list(i)) for i in comb(nums,3) if sum(i)==0] [[-1, 0, 1], [-1, -1, 2], [-1, 0, 1]] >>>
引入一个tmp列表，去掉重复元素，得到正确的最终结果：
>>> tmp = [sorted(list(i)) for i in comb(nums,3) if sum(i)==0] >>> result = [] >>> [result.append(i) for i in tmp if i not in result] [None, None] >>> result [[-1, 0, 1], [-1, -1, 2]] >>>
注：列表作元素的列表是不能用set()转换的办法来去重的。
>>> tmp = [[-1, 0, 1], [-1, -1, 2], [-1, 0, 1]] >>> set(tmp) Traceback (most recent call last): File "<pyshell#78>", line 1, in <module> set(tmp) TypeError: unhashable type: 'list' >>>
方法二：借用第一题中的自定义函数，改造可以返回多个答案的。因为a+b+c=0，所以新建一个函数Sum3()，功能是在先取出数a后调用Sum2() 在余下的数中再取2个满足target=-a的数即可。
>>> def Sum2(nums, target): res = [] for i,n in enumerate(nums): m = target - n t = nums[i+1:] if m in t: res.append([n,m]) return res >>> def Sum3(nums): tmp,res = [],[] for i in range(len(nums)-2): t = Sum2(nums[i+1:],-nums[i]) if t: tmp.extend([sorted([nums[i]]+j) for j in t]) for i in tmp: if i not in res: res.append(i) return res >>> nums = [-1, 0, 1, 2, -1, -4] >>> Sum3(nums) [[-1, 0, 1], [-1, -1, 2]] >>> >>> nums = [-1, 0, 1, 2, -1, -4, 4, -2, 3] >>> Sum3(nums) [[-1, 0, 1], [-1, -1, 2], [-2, -1, 3], [-2, 0, 2], [-4, 0, 4], [-4, 1, 3]] >>>
3Sum Closest
Given an array nums of n integers and an integer target, find three integers in nums such that the sum is closest to target. Return the sum of the three integers. You may assume that each input would have exactly one solution. [#16]
Example: Given array nums = [-1, 2, 1, -4], and target = 1. The sum that is closest to the target is 2. (-1 + 2 + 1 = 2).
>>> from itertools import combinations as comb >>> nums = [-1, 2, 1, -4] >>> target = 1 >>> [list(i) for i in comb(nums,3)] [[-1, 2, 1], [-1, 2, -4], [-1, 1, -4], [2, 1, -4]] >>> [(abs(sum(i)-target),list(i)) for i in comb(nums,3)] [(1, [-1, 2, 1]), (4, [-1, 2, -4]), (5, [-1, 1, -4]), (2, [2, 1, -4])] >>> t = [(abs(sum(i)-target),list(i)) for i in comb(nums,3)] >>> min(t) (1, [-1, 2, 1]) >>> min(t)[1] [-1, 2, 1] >>>
4Sum
Given an array nums of n integers and an integer target, are there elements a, b, c, and d in nums such that a + b + c + d = target? Find all unique quadruplets in the array which gives the sum of target. [#18]
Note:
The solution set must not contain duplicate quadruplets.
Example: Given array nums = [1, 0, -1, 0, -2, 2], and target = 0. A solution set is: [ [-1, 0, 0, 1], [-2, -1, 1, 2], [-2, 0, 0, 2] ]
题意：在列表中找出4个元素，使其和等于目标值。注意结果不能有相同四元组。
>>> from itertools import combinations as comb >>> nums = [1, 0, -1, 0, -2, 2] >>> target = 0 >>> result = [] >>> [result.append(sorted(list(n))) for n in comb(nums,4) if n not in result and sum(n)==target] [None, None, None] >>> result [[-1, 0, 0, 1], [-2, -1, 1, 2], [-2, 0, 0, 2]] >>>
相关单词
array : 数组
英 [əˈreɪ] 美 [əˈreɪ]
n.大堆;大群;大量;数组;阵列
vt.布置;排列;配置(兵力)
integer : 整数
英 [ˈɪntɪdʒə(r)] 美 [ˈɪntɪdʒər]
n.整数
indices : 索引，指数
英 [ˈɪndɪsiːz] 美 [ˈɪndɪsiːz]
index的名词复数形式之一，也可用indexes
index : 索引
英 [ˈɪndeks] 美 [ˈɪndeks]
n.(物价和工资等的)指数;指标;索引;标志;表征;量度
vt.为…编索引;将…编入索引;将(工资等)与(物价水平等)挂钩;使指数化
specific : 特定的
英 [spəˈsɪfɪk] 美 [spəˈsɪfɪk]
adj.具体的;特定的;特有的;明确的;独特的
n.特效药;特性;细节;显著的性质;特性
词根-speci- 种类
后缀-fic 具有某种性质的
assume : 假定
英 [əˈsjuːm] 美 [əˈsuːm]
v.假定;假设;认为;承担(责任);就(职);取得(权力);呈现(外观、样子);显露(特征)
前缀as- 表加强
词根-sum- 拿，取
exactly : 精确地
英 [ɪɡˈzæktli] 美 [ɪɡˈzæktli]
adv.确切地;准确地;精确地;(要求得到更多信息)究竟，到底;
(答语，表示赞同或强调正确)一点不错，正是如此，完全正确
前缀ex- 表加强
词根-act- 做
后缀-ly 表副词
solution : 解决方案
英 [səˈluːʃn] 美 [səˈluːʃn]
n.解决方案;溶液;解;解决办法;处理手段;答案;谜底
词根-solu- 松开
后缀-tion 表名词
element : 元素
英 [ˈelɪmənt] 美 [ˈelɪmənt]
n.要素;基本部分;典型部分;少量;有点;有些;(大团体或社会中的)一组，一群，一伙
