两数之和(leetCode-1)
题目如下图:(也可以到leetCode上看完整题目,题号1)
解答方法一:
最简单的方法就是双指针遍历数组.代码如下
- (NSMutableArray *)sumOfTwoNumbers:(NSMutableArray *)array target:(int)target
{NSMutableArray * resultArray = [[NSMutableArray alloc]init];for (int i = 0; i < array.count; i ++) //这里其实可以写i< array.cout-1;{for (int j = i +1; j < array.count; j ++){if ([array[i] intValue] + [array[j] intValue] == target){resultArray[0] = [NSString stringWithFormat:@"%d",i];resultArray[1] = [NSString stringWithFormat:@"%d",j];//题干写了必有且只有一个答案,所以不判断其余情况了return resultArray;;}}}return resultArray;
}一般双指针循环的时间复杂度比较大,我们来算一个上面代码的时间复杂度为:
n+(n-1)+(n-2)+……1, 是一个等差数列,所以根据等差数列求和公式:Sn = n/2 x (1+n), 结果为二分之n的平方,
根据大O渐近表示法;二分之一可以忽略,所以这个方法的时间复杂度为 n的平方.
(PS:大多数的双指针循环时间复杂度都为 n的平方)
这个运行时间比较长,所以不太推荐.
解答方法二:
使用一个循环遍历+存储方法
原理:
1.将遍历数组,以数组的元素为key,index为value,将其存入到NSMutableDictionary;
(PS:使用这个存储方法是因为题干说了,数组的元素不会重复出现. 如果数组里的元素重复出现,例如数组里有两个3,则不可以使用这个方法,因为NSMutableDictionary 的key是唯一的)
2.使用目标值-当前遍历的元素值,判断他们的差值在不在NSMutableDictionary里面,如果在,则说明已经存入了,则取出相对性的value即可;如果不在,则继续遍历.
3.继续重复进行步骤2.
代码如下:
- (NSMutableArray *)sumOfTwoNumbers:(NSMutableArray *)array target:(int)target
{NSMutableArray * resultArray = [[NSMutableArray alloc]init];NSMutableDictionary * dic = [[NSMutableDictionary alloc]init];for (int i = 0; i < array.count; i ++){//1.以数组元素值为key,以index(即i)为value[dic setValue: [NSString stringWithFormat:@"%d",i] forKey:array[i]];//2.目标值-当前遍历到的值,就等于另一个值tempNumint tempNum = target - [array[i] intValue];/*只需要判断另一个值tempNum有没有存入dic里,如果有存入,那么可以取出的value,如果还未存入,则取出的value为null*/NSString * tempStr = [dic objectForKey:[NSString stringWithFormat:@"%d",tempNum]];if (tempStr.length != 0){resultArray[0] = [NSString stringWithFormat:@"%d",i];resultArray[1] = tempStr;}}return resultArray;
}这个解法只进行了一个遍历,所以时间负责度为 O(n)