两数之和 II - 输入有序数组 Two Sum II - Input Array Is Sorted

问题描述

靠拢型双指针

典型的双指针问题, 就不过多介绍了, 详细的分析看这里.

#![allow(unused)]
fn main() {
// 靠拢型双指针
pub fn two_sum1(numbers: Vec<i32>, target: i32) -> Vec<i32> {
    assert!(numbers.len() >= 2);

    let mut left = 0;
    let mut right = numbers.len() - 1;

    while left < right {
        // 判定条件就其和为0
        let sum = numbers[left] + numbers[right];
        match sum.cmp(&target) {
            Ordering::Less => left += 1,
            Ordering::Greater => right -= 1,
            Ordering::Equal => {
                return vec![left as i32 + 1, right as i32 + 1];
            }
        }
    }

    Vec::new()
}
}

二分查找法

因为数组已经是排好序的了, 也可以先遍历数组, 并用二分查找法找到其和为 target 的对应的元素.

要注意的是, 二分查找法对于有很多的重复元素时, 需要做一下优化, 我们在这里并没有手动实现二分查找法, 而只是调用了 Rust 的 slice::binary_search() 方法.

#![allow(unused)]
fn main() {
// 二分查找法
pub fn two_sum2(numbers: Vec<i32>, target: i32) -> Vec<i32> {
    for (index, &num) in numbers.iter().enumerate() {
        // 从下个元素开始使用二分查找法, 搜索对应的元素.
        if let Ok(slice_index) = numbers[index + 1..].binary_search(&(target - num)) {
            // 更新索引值.
            let next_index = slice_index + index + 1;
            return vec![index as i32 + 1, next_index as i32 + 1];
        }
    }

    Vec::new()
}