力扣 1 两数之和 C python

力扣 1 两数之和

有理解不对的地方欢迎指正。

给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。

你可以假设每种输入只会对应一个答案。但是，你不能重复利用这个数组中同样的元素。

示例:

给定 nums = [2, 7, 11, 15], target = 9

因为 nums[0] + nums[1] = 2 + 7 = 9

所以返回 [0, 1]

暴力解法：

C

int* twoSum(int* nums, int numsSize, int target, int* returnSize){

int i,j;

int *a=NULL; //可改成 static int a[2]={0};

returnSize=2; //无此会输出[ ] ,返回值的个数

for(i=0;i<numsSize-1;i++)

{

for(j=i+1;j<numsSize;j++)

{

if(nums[i]+nums[j]==target)

{

result=(int)malloc(sizeof(int)*2);

a[0]=i;

a[1]=j;

return a;

}

}

}

return a;

}

//若将函数改为 int* twoSum(int* nums, int numsSize, int target)，会报错 too many arguments to function 'twoSum‘

两个return a; 第一个在if里，若不满足条件也需返回结果。

执行结果：

执行用时 :

208 ms, 在所有 C 提交中击败了49.95%的用户

内存消耗 :7.7 MB, 在所有 C 提交中击败了11.05%用户

此方法运行速度慢有待改进。

利用哈希表法:

int* twoSum(int* nums, int numsSize, int target) {

      int min = 2147483647;
      int i = 0;
      for (i = 0; i < numsSize; i++) {
          if (nums[i] < min)
              min = nums[i];//找最小值
      }
      int max = target - min;
      int len = max - min + 1;   //确定hash长度，最大减最小可确定两数之间有多少值以此创建哈希表
      int *table = (int*)malloc(len*sizeof(int));
      int *indice = (int*)malloc(2*sizeof(int));//返回的
      for (i = 0; i < len; i++) {
          table[i] = -1;         //hash初值，哈希表初始化
      }
      for (i = 0; i < numsSize; i++) {
          if (nums[i]-min < len) {
              if (table[target-nums[i]-min] != -1) {       //target-num[i]-min 可把nums[i]-min看做一个整体，可写为target-num[i]或target-min，但之前有num[i]-min<len来判断,进行查找是否有满足条件的
                    //满足相加为target，若等于-1则还是初值，若相加为target，之前的第一个值已经被记录在哈希表内，找到第二个数就是查找到满足条件结果，使table[key]=value.两数互相选择配对
                  indice[0] = table[target-nums[i] - min];//满足上述条件， table[target-nums[i] - min]是value是对应的下标。得到第一个数的下标
                  indice[1] = i;
                  return indice;
              }
              table[nums[i]-min] = i;//不满足!=-1时，即相加不为target时调至这里，将i赋值到哈希表table[nums[i]-min]内,赋值前table[nums[i]-min]还是初值-1，则table的value为此时i，key为nums[i]-min (nums[i]-min 可看为nums[i]),这样就在哈希表内存入一对键值，则就这样进行边存入边查找操作，还能以防冲突。
          }
      }
      free(table);
      return indice;
    }

int main() {

       int a[4] = {8,5,1,13};
       int tag = 9;
       int *num = twoSum(a,4,tag);
          printf("%d-%d",num[0],num[1]);

       return 0;
    }


           

Python:

class Solution(object):

def twoSum(self, nums, target):

“”"

:type nums: List[int]

:type target: int

:rtype: List[int]

“”"

for i in range(len(nums)):

for l in range(len(nums)-1):

if nums[i]+nums[l]==target and i!=l:

a=[i,l]

return a

python的暴力解法更慢。

Python enumerate() 函数

描述

enumerate() 函数用于将一个可遍历的数据对象(如列表、元组或字符串)组合为一个索引序列，同时列出数据和数据下标，一般用在 for 循环当中。

Python 2.3. 以上版本可用，2.6 添加 start 参数。

语法

以下是 enumerate() 方法的语法:

enumerate(sequence, [start=0])

参数

sequence – 一个序列、迭代器或其他支持迭代对象。

start – 下标起始位置。

返回值

返回 enumerate(枚举) 对象。

实例

以下展示了使用 enumerate() 方法的实例：

seasons = [‘Spring’, ‘Summer’, ‘Fall’, ‘Winter’]

list(enumerate(seasons))

[(0, ‘Spring’), (1, ‘Summer’), (2, ‘Fall’), (3, ‘Winter’)]

list(enumerate(seasons, start=1)) # 下标从 1 开始

[(1, ‘Spring’), (2, ‘Summer’), (3, ‘Fall’), (4, ‘Winter’)]

普通的 for 循环

i = 0

seq = [‘one’, ‘two’, ‘three’]

for element in seq:

… print i, seq[i]

… i +=1

…

0 one

1 two

2 three

for 循环使用 enumerate

seq = [‘one’, ‘two’, ‘three’]

for i, element in enumerate(seq):

… print i, element

…

0 one

1 two

2 three

python 哈希表 （转载）

class Solution(object):

def twoSum(self, nums, target):

dic = {}

for i, num in enumerate(nums):

if num in dic:

return [dic[num], i]

else:

dic[target - num] = i