167.two-sum-ii-input-array-is-sorted.md

問題

https://leetcode.com/problems/two-sum-ii-input-array-is-sorted/

回答

初回の回答:

わからなかったので回答見た。両端の数を足した値と target を比較して、等しければそれが答え、小さければ右端の index を -1、小さければ左端の index を +1 する。それは二分探索ではないような…。計算量は最悪のケースで$\mathcal{O}(n)$。

impl Solution {
    pub fn two_sum(numbers: Vec<i32>, target: i32) -> Vec<i32> {
        let mut l = 0;
        let mut r = numbers.len() - 1;
        while l < r {
            let sum = numbers[l] + numbers[r];
            if sum == target {
                return vec![l as i32 + 1, r as i32 + 1];
            }
            if sum < target {
                l += 1;
            } else {
                r -= 1;
            }
        }
        vec![-1, -1]
    }
}