问题描述:给定一组指定整数数组,找出数组中加和等于特定数的两个数。
函数(方法)twoSum返回这两个数的索引,index1必须小于index2。
另外:你可以假设一个数组只有一组解。
一个栗子:
Input: numbers={2, 7, 11, 15}, target=9 Output: index1=1, index2=2
算法实现如下:
1 /** 2 * 时间复杂度O(n) 3 * @param array 4 * @param target 5 * @return Map<Integer,Integer> 6 */ 7 public static Map<Integer, Integer> twoSum(int[] array, int target) { 8 9 //Map<value,index>10 Map<Integer, Integer> result = new HashMap<Integer, Integer>();11 12 Map<Integer, Integer> container = new HashMap<Integer, Integer>();13 for (int i = 0; i < array.length; i++) {14 if (!container.containsKey(target - array[i])) {15 container.put(array[i], i + 1);16 } else {17 result.put(target - array[i], container.get(target - array[i]));18 result.put(array[i], i + 1);19 break ;20 }21 }22 23 return result;24 }
另有双层循环判断的算法实现,时间复杂度为O(n²),在此就不列出。
关于时间复杂度的计算
一个栗子:
1 int value = 0 ; //该代码执行1次2 for(int i = 0 ; i < n ; i++){ 3 value += n ; //该代码执行n次4 }
该算法执行1+n次,如果n趋近于无穷大,1便可忽略不计,也就是说该算法执行了n次。时间复杂度常用O符号表示,这个算法的时间复杂度为O(n)。
当一个算法的计算时间复杂度时,可以遵循这样的规则:
1).去掉运行时间中的所有加法常数。
2).只保留最高阶项。
3).如果最高阶项存在且不是1,去掉与这个最高阶相乘的常数得到时间复杂度
再一个栗子
1 for (int i = 0; i < n; i++) {2 for (int j = i; j < n; j++) {3 // do something4 }5 }
当 i = 0 时 里面的fo循环执行了n次,当i等待1时里面的for循环执行了n - 1次,当i 等于2里里面的fro执行了n - 2次........所以执行的次数是:
n + (n-1) + (n-2) + ...+ 1
= n(n+1)/2
= n²/2 + n/2
根据我们上边的时间复杂度算法
1.去掉运行时间中的所有加法常数: 没有加法常数不用考虑
2.只保留最高阶项: 只保留 n²/2
3. 去掉与这个最高阶相乘的常数: 去掉 1/2 只剩下 n²
最终这个算法的时间复杂度为O(n²)
原标题:LeetCode第一题以及时间复杂度的计算
关键词:时间