青岛seo推广公司,seo诊断报告示例,免费的wordpress采集,做网站的上市公司求#xff1a;给你一个整数数组 arr#xff0c;请你检查是否存在两个整数 N 和 M#xff0c;满足 N 是 M 的两倍(即#xff0c;N 2 * M)。更正式地#xff0c;检查是否存在两个下标 i 和 j 满足#xff1a;i ! j0 i, j arr.lengtharr[i] 2 * arr[j]示例 1给你一个整数数组 arr请你检查是否存在两个整数 N 和 M满足 N 是 M 的两倍(即N 2 * M)。更正式地检查是否存在两个下标 i 和 j 满足i ! j0 i, j arr.lengtharr[i] 2 * arr[j]示例 1输入arr [10,2,5,3]输出true解释N 10 是 M 5 的两倍即 10 2 * 5 。示例 2输入arr [7,1,14,11]输出true解释N 14 是 M 7 的两倍即 14 2 * 7 。示例 3输入arr [3,1,7,11]输出false解释在该情况下不存在 N 和 M 满足 N 2 * M 。提示2 arr.length 500-10^3 arr[i] 10^3解首先最直观的想到暴力法时间复杂度是O(N^2)boolcheckIfExist(int* arr,intarrSize){inti,j;for(i0;ifor(ji1;jif(arr[i]arr[j]*2|| arr[j]arr[i]*2)returntrue;}returnfalse;}对暴力法进行改进很自然的想到使用哈希表以空间换时间的策略通过判断哈希表对应位置上的索引关系能够知道是否存在符合题意的一对数。注意这里有2个细节1、数组可能包含数组而使用数组实现哈希表索引不能是负数但是因为题目给出了数的范围我们对这个区间统一加上1000就可以保证索引的有效性。2、0要单独处理否则会因为0的存在导致错误的结果。boolcheckIfExist(int* arr,intarrSize){inthashMap[2001] {0};intcountZero 0;inti;for(i0;iif(arr[i]0) countZero;if(countZero2)returntrue;hashMap[1000arr[i]] 1;}for(i0;iif(arr[i]!0 arr[i]%20 hashMap[1000arr[i]/2]1)returntrue;returnfalse;}
