笔试的时候刚好做到这道题:定一个整型数组(数组中的元素可重复,已排序)鉯及一个指定的值。找出数组中两数之和为指定值的所有整数对要求时间复杂度为O(N)。
首先来分析一下这个题假设题目没有说已排序和時间复杂度的要求,那么用最暴力的方法就是直接遍历两次数组时间复杂度为O(N*N)。这里也来实现一下代码如下:
/*暴力法,直接遍历两次數组时间复杂度为O(n*n)*/
}
如果题目没有写明已排序,那么可以先将整型数组排序排序之后定义两个指针left和right。left指向已排序数组中的第一个元素right指向已排序数组中的最后一个元素,将 arr[left]+arr[right]与
给定的元素比较若前者大,right--;若前者小left++;若相等,则找到了一对整数之和为指定值的元素此方法采用了排序,排序的时间复杂度为O(NlogN)排序之后扫描整个数组求和比较的时间复杂度为O(N)。故总的时间复杂度为O(NlogN)空间复杂度为O(1)。
那麼现在题目中已经写明已排序所以就可以直接用上面的思路进行实现,那么时间复杂度就是O(N)接下来附上我的代码实现: