167.两数之和II-输入有序数组

链接：167.两数之和II-输入有序数组
难度：Medium
标签：数组、双指针、二分查找
简介：给定一个已按照升序排列 的有序数组，找到两个数使得它们相加之和等于目标数。

题解 1 - typescript

• 编辑时间：2020-07-20
• 执行用时：108ms
• 内存消耗：38.1MB
• 编程语言：typescript
• 解法介绍：二分查找。

function twoSum(numbers: number[], target: number): number[] {
  const len = numbers.length;
  for (let i = 0; i < len; i++) {
    const index = _find(target - numbers[i], i + 1);
    if (index !== -1) return [i + 1, index + 1];
  }
  return [];
  function _find(num: number, l: number = 0, r: number = len): number {
    if (l >= r) return -1;
    const mid = (l + r) >> 1;
    const val = numbers[mid];
    if (val < num) return _find(num, mid + 1, r);
    else if (val > num) return _find(num, l, mid);
    else return mid;
  }
}

题解 2 - cpp

• 编辑时间：2023-07-08
• 执行用时：8ms
• 内存消耗：15.2MB
• 编程语言：cpp
• 解法介绍：二分。

class Solution {
public:
    vector<int> twoSum(vector<int>& numbers, int target) {
        int n = numbers.size();
        for (int i = 0; i < n; i++) {
            int l = i + 1, r = n;
            while (l < r) {
                int m = (l + r) / 2, val = numbers[m] + numbers[i];
                if (val < target) l = m + 1;
                else r = m;
            }
            if (l != n && numbers[i] + numbers[l] == target) return { i + 1, l + 1};
        }
        return {};
    }
};

题解 3 - python

• 编辑时间：2023-07-08
• 执行用时：112ms
• 内存消耗：17.1MB
• 编程语言：python
• 解法介绍：同上。

class Solution:
    def twoSum(self, numbers: List[int], target: int) -> List[int]:
        n = len(numbers)
        for i in range(n):
            l = i + 1
            r = n
            while l < r:
                m = (l + r) // 2
                val = numbers[i] + numbers[m]
                if val < target:
                    l = m + 1
                else:
                    r = m
            if l != n and numbers[i] + numbers[l] == target:
                return [i+1, l+1]
        return []

题解 4 - rust

• 编辑时间：2023-07-08
• 执行用时：4ms
• 内存消耗：2.1MB
• 编程语言：rust
• 解法介绍：同上。

impl Solution {
    pub fn two_sum(numbers: Vec<i32>, target: i32) -> Vec<i32> {
        let n = numbers.len();
        for i in 0..n {
            let mut l = i + 1;
            let mut r = n;
            while l < r {
                let m = (l + r) / 2;
                let val = numbers[i] + numbers[m];
                if val < target {
                    l = m + 1;
                } else {
                    r = m;
                }
            }
            if l != n && numbers[i] + numbers[l] == target {
                return vec![(i as i32) + 1, (l as i32) + 1];
            }
        }
        return vec![];
    }
}