整数配列と整数を指定し、指定した整数に等しい2つの配列のインデックスを返します.最適なアルゴリズムを必要として,アルゴリズムの空間と時間の複雑さを分析します

673 ワード

テーマ:整数配列と整数を指定し、指定した整数に等しい2つの配列のインデックスを返します.最適なアルゴリズムを必要として,アルゴリズムの空間と時間の複雑さを分析します
参考答案:
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)である