两数之和

74次阅读

共计 599 个字符,预计需要花费 2 分钟才能阅读完成。

算法
题目:引用:https://leetcode-cn.com/probl… 具体题目:给定一个整数数组 nums 和一个目标值 target,请你在该数组中找出和为目标值的那 两个 整数,并返回他们的数组下标。你可以假设每种输入只会对应一个答案。但是,你不能重复利用这个数组中同样的元素。
给定 nums = [2, 7, 11, 15], target = 9
因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]
代码:
public class SumFind {

private int[] find(int[] resource, int target) {

int[] index = new int[2];

for (int i = 0; i < (resource.length – 2); i++) {

if (resource[i] <= target) {

for (int j = i + 1; j < resource.length – 1; j++) {

if (target == (resource[i] + resource[j])) {

index[0] = i;
index[1] = j;

}

}

}

}

return index;
}
}

最好时间复杂度:数组里面的元素都大于目标数,所以不会去循环里面的代码,所以复杂度就是外面的循环就是 N -1,也就是 O(n)
最坏时间复杂度:把里面的每一个循环完之后才找到这两个数。所以每一次循环就是 n + (n-1) + (n-2) + … + 1(1 + n) /2, 也是 O(n).

正文完
 0