手稿_V1.11
需积分: 0 163 浏览量
2022-08-03
12:13:44
上传
评论
收藏 209KB PDF 举报
分析:
方法一:逐一遍历所有的双整数对,根据排列组合公式,最多需要比较 次,即时间复杂度为 ;
方法二:hash表,先把数组数据hash化(key为数组数据,value为数组索引),逐一遍历元素,由于要规避
重复元素,就一边hash一边进行比较.
若target-当前元素的hash值在表中已经存在,就直接存储数据进行返回;
若target-当前元素的hash值在表中不存在,就把当前元素及其在数组中的索引保存到hash表
中;
循环遍历直到所有元素遍历完成,最差情况下,时间复杂度为 ,由于要额外申请hash表空间,
最差情况下,空间复杂度为 .
要用到哈希表这种数据结构，使用C++语言比较合适
方法三：回溯法.果断超时了，时间复杂度为
方法一:C_逐一遍历双整数对
/*
给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整
数，并返回他们的数组下标。
你可以假设每种输入只会对应一个答案。但是，你不能重复利用这个数组中同样的元素。
示例:
给定 nums = [2, 7, 11, 15], target = 9
因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/two-sum
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
*/
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
/**
* Note: The returned array must be malloced, assume caller calls free().
*/
int* twoSum( int* nums ,
int numsSize ,
int target ,
int* returnSize
)
{
int i = 0 ;
int j = 0 ;
int* index = (int*)malloc(2*sizeof(int)) ;
int valid = 0 ;
for(i = 0; i < numsSize ;i++)
{
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
评论0