剑指 Offer II 006-排序数组中两个数字之和
发表于：2021-12-03 | 分类： 简单
字数统计: 1.8k | 阅读时长: 9分钟 | 阅读量：

原文链接: https://leetcode-cn.com/problems/kLl5u1

中文题目

给定一个已按照 升序排列  的整数数组 numbers ，请你从数组中找出两个数满足相加之和等于目标数 target 。

函数应该以长度为 2 的整数数组的形式返回这两个数的下标值。numbers 的下标 从 0 开始计数 ，所以答案数组应当满足 0 <= answer[0] < answer[1] < numbers.length 。

假设数组中存在且只存在一对符合条件的数字，同时一个数字不能使用两次。

 

示例 1：

输入：numbers = [1,2,4,6,10], target = 8
输出：[1,3]
解释：2 与 6 之和等于目标数 8 。因此 index1 = 1, index2 = 3 。

示例 2：

输入：numbers = [2,3,4], target = 6
输出：[0,2]

示例 3：

输入：numbers = [-1,0], target = -1
输出：[0,1]

 

提示：

  • 2 <= numbers.length <= 3 * 104
  • -1000 <= numbers[i] <= 1000
  • numbers 按 递增顺序 排列
  • -1000 <= target <= 1000
  • 仅存在一个有效答案

 

注意：本题与主站 167 题相似（下标起点不同）：https://leetcode-cn.com/problems/two-sum-ii-input-array-is-sorted/

通过代码

高赞题解

1. 题目讲解

如果你已经理解了题目，这个视频可以跳过

...之和变形一：输入有序数组题目讲解.mp4

2. 方案一：二分查找，请看视频：

2_两数之和变形一：二分查找方法.mp4

代码如下：

[]
// 时间复杂度：O(nlogn)
// 空间复杂度：O(1)
public int[] twoSum(int[] nums, int target) {
    if (nums == null || nums.length == 0) return new int[0];

    for (int i = 0; i < nums.length; i++) {
        int x = nums[i];
        // 线性查找 - O(n)
        // 1. 二分查找 - O(logn)
        // [i + 1, nums.length - 1] 区间二分查找 target - x
        int index = binarySearch(nums, i + 1, nums.length - 1, target - x);
        if (index != -1) {
            return new int[]{i, index};
        }
    }

    return new int[0];
}

private int binarySearch(int[] nums, int left, int right, int target) {
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] == target)
            return mid;
        if (nums[mid] > target)
            right = mid - 1;
        else
            left = mid + 1;
    }
    return -1;
}
[]
public:
    // 二分查找
    // 时间复杂度：O(nlogn)
    // 空间复杂度：O(1)
    vector<int> twoSum1(vector<int>& numbers, int target) {
        for (int i = 0; i < numbers.size(); i++) {
            int x = numbers[i];
            // 线性查找 - O(n)
            // 1. 二分查找 - O(logn)
            // [i + 1, numbers.length - 1] 区间二分查找 target - x
            int index = binarySearch(numbers, i + 1, numbers.size() - 1, target - x);
            if (index != -1) {
                return {i, index};
            }
        }

        return {};
    }

    int binarySearch(vector<int>& nums, int left, int right, int target) {
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] == target)
                return mid;
            if (nums[mid] > target)
                right = mid - 1;
            else
                left = mid + 1;
        }
        return -1;
    }
[]
# 二分查找
# 时间复杂度：O(nlogn)
# 空间复杂度：O(1)
def twoSum1(self, numbers: List[int], target: int) -> List[int]:
    for i in range(len(numbers)):
        x = numbers[i]
        # 1. 二分查找 - O(logn)
        # [i + 1, nums.length - 1] 区间二分查找 target - x
        index = self.binary_search(numbers, i + 1, len(numbers) - 1, target - x)
        if index != -1:
            return [i, index]
    return []

def binary_search(self, numbers: List[int], left: int, right: int, target: int) -> int:
    while left <= right:
        mid = left + (right - left) // 2
        if target == numbers[mid]:
            return mid
        elif target > numbers[mid]:
            left = mid + 1
        else:
            right = mid - 1
    return -1
[]
// 二分查找
// 时间复杂度：O(nlogn)
// 空间复杂度：O(1)
var twoSum1 = function(numbers, target) {
    for (let i = 0; i < numbers.length; i++) {
        const x = numbers[i]
        const index = binarySearch(numbers, i + 1, numbers.length - 1, target - x)
        if (index != -1) {
            return [i, index]
        }
    }
    return []
};

var binarySearch = function(number, left, right, target) {
    while (left <= right) {
        const mid = left + Math.floor((right - left) / 2)
        if (target == number[mid]) {
            return mid;
        } else if (target < number[mid]) {
            right = mid - 1
        } else {
            left = mid + 1
        }
    }
    return -1
}
[]
// 方法一：严格的二分查找
// 时间复杂度：O(nlogn)
// 空间复杂度：O(1)
func twoSum1(numbers []int, target int) []int {
    for i := range numbers {
        var x = numbers[i]
        // 线性查找 - O(n)
        // 1. 二分查找 - O(logn)
        // [i + 1, nums.length - 1] 区间二分查找 target - x
        var index = binarySearch(numbers, i + 1, len(numbers) - 1, target - x)
        if index != -1 {
            return []int{i + 1, index + 1}
        }
    }
    return []int{}
}

func binarySearch(numbers []int, left int, right int, target int) int {
    for left <= right {
        var mid = left + (right - left) / 2
        if numbers[mid] == target {
            return mid
        } else if numbers[mid] > target {
            right = mid - 1
        } else {
            left = mid + 1
        }
    }
    return -1
}

3. 方案二：双指针， 请看视频：

..._两数之和变形一：双指针技巧解法.mp4

代码如下：

[]
// 时间复杂度：O(n)
// 空间复杂度：O(1)
public int[] twoSum(int[] nums, int target) {
    if (nums == null || nums.length == 0) return new int[0];

    int left = 0;
    int right = nums.length - 1;
    while (left < right) {
        int sum = nums[left] + nums[right];
        if (sum == target) {
            return new int[]{left, right};
        } else if (sum < target) {
            left++;
        } else {
            right--;
        }
    }

    return new int[0];
}
[]
public:
    // 双指针
    // 时间复杂度：O(n)
    // 空间复杂度：O(1)
    vector<int> twoSum(vector<int>& numbers, int target) {
        int left = 0, right = numbers.size() - 1;
        while (left < right) {
            int sum = numbers[left] + numbers[right];
            if (sum == target) {
                return {left, right};
            } else if (sum < target) {
                left++;
            } else {
                right--;
            }
        }
        return {};
    }
[]
# 双指针
# 时间复杂度：O(n)
# 空间复杂度：O(1)
def twoSum(self, numbers: List[int], target: int) -> List[int]:
    left, right = 0, len(numbers) - 1
    while left < right:
        sum = numbers[left] + numbers[right]
        if sum == target:
            return [left, right]
        elif sum < target:
            left = left + 1
        else:
            right = right - 1
    return []
[]
// 双指针
// 时间复杂度：O(n)
// 空间复杂度：O(1)
var twoSum = function(numbers, target) {
    let left = 0, right = numbers.length - 1
    while (left < right) {
        const sum = numbers[left] + numbers[right]
        if (sum == target) {
            return [left, right]
        } else if (sum < target) {
            left++
        } else {
            right--
        }
    }
    return []
};
[]
// 双指针
// 时间复杂度：O(n)
// 空间复杂度：O(1)
func twoSum(numbers []int, target int) []int {
    var left, right = 0, len(numbers) - 1
    for left < right {
        var sum = numbers[left] + numbers[right]
        if sum == target {
            return []int{left + 1, right + 1}
        } else if sum < target {
            left++
        } else {
            right--
        }
    }
    return []int{}
}

类似的题目最好是一起刷，这样可以提高刷题效率：

  1. leetcode 1 号算法题：两数之和
  2. leetcode 167 号算法题：两数之和Ⅱ - 输入有序数组
  3. leetcode 170 号算法题：两数之和Ⅲ - 数据结构设计
  4. leetcode 653 号算法题：两数之和Ⅳ - 输入 BST
  5. leetcode 15 号算法题：三数之和
  6. leetcode 18 号算法题：四数之和

在刷题的时候：

  1. 如果你觉得自己数据结构与算法基础不够扎实，那么请点这里，这里包含了一个程序员 5 年内需要的所有算法知识

  2. 如果你感觉刷题太慢，或者感觉很困难，或者赶时间，那么请点这里。这里用 365 道高频算法题，带你融会贯通算法知识，做到以不变应万变

  3. 回溯、贪心和动态规划，是算法面试中的三大难点内容，如果你只是想搞懂这三大难点内容 请点这里

以上三个链接中的内容，都支持 Java/C++/Python/js/go 五种语言

统计信息

通过次数 提交次数 AC比率
11130 17066 65.2%

提交历史

提交时间 提交结果 执行时间 内存消耗 语言
数组 二分查找 双指针
上一篇:
剑指 Offer II 005-单词长度的最大乘积
下一篇:
剑指 Offer II 007-数组中和为 0 的三个数
本文目录
本文目录
    •
    本站总访问量： 次 |
    Copyright © 2020 - 2021 枫奇丶宛南 | Powered by Hexo | Theme Bamboo