整数配列と整数を指定し、指定した整数に等しい2つの配列のインデックスを返します.最適なアルゴリズムを必要として,アルゴリズムの空間と時間の複雑さを分析します
673 ワード
テーマ:整数配列と整数を指定し、指定した整数に等しい2つの配列のインデックスを返します.最適なアルゴリズムを必要として,アルゴリズムの空間と時間の複雑さを分析します
参考答案:
解析:空間的複雑度と時間的複雑度はいずれもO(n)である
参考答案:
public static int[] twoSum(int[] numbers, int target) {
int i = 0, j = numbers.length - 1;
while (i != j) {
if (numbers[i] + numbers[j] == target) {
return new int[]{i + 1, j + 1};
}
if (numbers[i] + numbers[j] < target) {
i++;
continue;
}
if (numbers[i] + numbers[j] > target) {
j--;
continue;
}
}
return new int[]{i, j};
}
解析:空間的複雑度と時間的複雑度はいずれもO(n)である