题目的简介
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.
example
Given nums = [2, 7, 11, 15], target = 9,
Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].
就是为了取得一个数组中任意两个不相同的数的和和所给数相同的这两个数字
的位置，返回的是一个数组有两个元素
c 语言的解法
(利用的是自己构建hash list；利用的是链式)
链式:当求余的时候余数相同，形成链表查找的时候利用链表查找
#include <stdio.h>
#include <stdlib.h>
typedef struct hash_list_node* hlp;//hash_list_point哈希节点指针
typedef struct hash_list_node
{
int index;
hlp next;
}hln;
//构建hash节点包括指向下一个的指针和存储的值
void hash_list_free(hlp hash_list,int list_length_prime)
{
int address = 0;
for(address = 0;address < list_length_prime;++address)
{
hlp next_node = hash_list[address].next;
while(next_node != NULL)
{
hlp tempt = next_node;
next_node = next_node->next;
free(tempt);
}
}
}
//清空hash 表（hln类型的数组）每一个节点都进行内存的释放free
int *twoSum(int *numbers,int n,int target)
{
if(numbers == NULL | n < 2)
return NULL;
int index = 0;
int hash_length = 293;
//hash表的长度决定的是整个程序的运行速度
//hash表的长度为素数
hlp hash_list = (hlp)malloc(sizeof(hln) * hash_length);
if(hash_list == NULL)
return NULL;
for(index = 0;index < hash_length;++index)
{
hash_list[index].index = -1;
hash_list[index].next = NULL;
}
//初始化hash表的值
for(index = 0;index < n;++index)
{
int hp = abs(numbers[index] % hash_length);//hash_list_position
//将numbers中的值映射到hash表中来
if(hash_list[hp].index == -1)//如果为空则直接映射到
hash_list[hp].index = index;
else//不是空则作为链表
{
hlp new_hash_node = (hlp)malloc(sizeof(hln));
//设置一个指向hln的指针(同时创建内存hln一个节点)
if(new_hash_node == NULL)//创建失败
{
hash_list_free(hash_list,293);
return NULL;
}
new_hash_node->index = index;
new_hash_node->next = hash_list[hp].next;
hash_list[hp].next = new_hash_node;
}
}
int* rect = (int*)malloc(sizeof(int)*2);
//创建返回的数组存储的是要求的位置信息
for(index = 0;index < n;++index)
{
int bias = abs((target - numbers[index]) % hash_length);
//遍历找到另一半
//其中在hash表中用的是数值求出的位置信息
if(hash_list[bias].index == -1)
continue;
if(numbers[hash_list[bias].index] == (target - numbers[index]) && hash_list[bias].index != index)
{
rect[0] = index;
rect[1] = hash_list[bias].index;
hash_list_free(hash_list,hash_length);
return rect;
}
else
{
hlp link_node = hash_list[bias].next;
while(link_node != NULL)
{
if(numbers[link_node->index] == (target - numbers[index]))
{
rect[0] = index;
rect[1] = link_node->index;
hash_list_free(hash_list,hash_length);
return rect;
}
else
{
link_node = link_node->next;
}
}
}
}
hash_list_free(hash_list,hash_length);
return NULL;
}
利用hash表将numbers中的数据的位置存储在hash中
当遍历numbers的时候，通过target数与当前的numbers的值的差值求出要找的
数的值，利用存储在hash表的情况的过程，找到hash表的一个‘单元号’，单元号的第一户我们判断是否为要的值，如果不是的话，我们通过遍历链表来找出本‘单元’的各户的值
python的解法
1 comb()函数
comb函数是一个generator，可以返回一个数列中的真子集
def comb(l,n):
if n == 0:
yield ()
else:
for i in range(len(l)):
for r in comb(l[i + 1:],n - 1):
yield (l[i],) + r
print(f.__next__())
#每一次都会返回所有结果的一个数
#l 为 一个 list[ ]
#n 为所要的子集的数列的个数
2 enumerate_list()函数
为了使得所给的list变成一个generator的object
并且返回的是所给的list的位置和value
def enumerate_list(l):
for i ,value in enumerate(l):
yield (i,),value
l = [1,2,3]
print(enumerate_list(l).__next__())
#((0,), 1) 可以看到格式是这样的，当给定一个list我们得到的格式
3 dict_append()函数
创建一个dict 将所给数列的数据的2倍与target的差作为:key
因为相加和为target的两个数据*2与target的差的值的绝对值(abs)相同
得到是这样类型的dict
{key : [((0,),1)],[ ],key :[ ]...... }
类似的结构
def dict_append(d,key,value):
d[key] = d.get(key.[]) + [value]
#get函数是在dict中找到key的值对应的list，如果不存在返回一个list[ ]
4 dict_add_by_distance()函数
dict_add_by_distance( ) 函数
传入的是被generator的tuble( (0, ),value )这种类型的
abs(2 * tuble[1] - target)：如果存在两个值相加为target则这个值相同
{key : [((0,),1)],[ ],key :[ ]...... }得到的最后数据结构
如果是在一个key里面的则可能是所要tuble 则tuble[0][0]则为所求的信息
def dict_add_by_distance(d,l,target):
for tuble in l:
dict_append(d,abs(2 * tuble[1] - target),tuble)
5 find_pairs(),find_all_pairs()函数
通过得到的dict取得其中的每一个元素判断几种特殊的情况 :
1.存在类似于 5 + 3 = 8 和 4 + 4 = 8的情况
2.单独存在4 + 4 = 8的情况
def find_pairs(l,target,size):
if len(l) <= 1:
return
#length为1的情况就是说在每一个dict中的list中元素只有一个
#就是说明这个值的2倍与target的差值这个值相同的元素只有一个
smaller = [tuble[0] for tuble in l if 2 *tuble[1] <= target ]
bigger = [tuble[0] for tuble in l if 2 *tuble[1] >= target]
for i in smaller:
for j in bigger:
if len(i) + len(j) != size:
continue
#为了判断的情况是情况 1 见上文
e = i + j
#得到的是一个tuble中包含两个值分别为要求的位置
if len(frozenset(e)) != size:
continue
#如果两个值相同set中自动去掉相同的元素
yield tuple(sorted(e))
#排序
def find_all_pairs(d,target,size):
for i in d.values():
for e in find_pairs(i,target,size):
yield e
主函数
整个函数的进程我们可以知道
举个例子num = [1,2,3] target = 3
1.先把给到的num变成generator //enumerate_list(num)
并且变成((0,),value)这种类型的样子
2.dict_add_by_distance( ) 中利用dict_append( )
利用的是generator num中的数据*2 - target得到的数字作为key
其中的每个key对应的是一个list
{key:[((0,),value)...] }每一个key中有一个list 每一个list中有的是多个tuble
每一个tuble代表的是2倍-target的值=key，并且具有的是tuble[0]为一个位置的tuble
tuble[1]value
3.得到了处理好的数据{key:[((0,),value)...] }：
之后进行寻找把每一个list拿出来如果list只有一个值的话则表示只有一个值不符合
4.返回之后的为tuble再list化
def two_sum(num,target):
d = {}
dict_add_by_distance(d,enumerate_list(num),target)
return list(list(set(find_all_pairs(d,target,2)))[0])
