小鲸鱼的梦境
0%

『LeetCode』167 两数之和 II - 输入有序数组

发表于 分类于 Valine：
本文字数： 4.2k 阅读时长 ≈ 4 分钟

题目

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

给你一个下标从 1 开始的整数数组 numbers ，该数组已按非递减顺序排列，请你从数组中找出满足相加之和等于目标数 target 的两个数。如果设这两个数分别是 \(numbers[index_{1}]\) 和 \(numbers[index_{2}]\) ，则 \(1 <= index_{1} < index_{2} <= numbers.length\) 。

以长度为 2 的整数数组 \([index_{1}, index_{2}]\) 的形式返回这两个整数的下标 \(index_{1}\) 和 \(index_{2}\)。

你可以假设每个输入 只对应唯一的答案 ，而且你 不可以 重复使用相同的元素。

你所设计的解决方案必须只使用常量级的额外空间。

示例 1：

输入：numbers = [2,7,11,15], target = 9
输出：[1,2]
解释：2 与 7 之和等于目标数 9 。因此 index1 = 1, index2 = 2 。返回 [1, 2] 。

示例 2：

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

示例 3：

输入：numbers = [-1,0], target = -1
输出：[1,2]
解释：-1 与 0 之和等于目标数 -1 。因此 index1 = 1, index2 = 2 。返回 [1, 2] 。

提示：

  • \(2 <= numbers.length <= 3 * 10^{4}\)
  • -1000 <= numbers[i] <= 1000
  • numbers 按 非递减顺序 排列
  • -1000 <= target <= 1000
  • 仅存在一个有效答案

标签

数组, 双指针, 二分查找

相似题目

题解

【两数之和 II - 输入有序数组】双指针+二分查找

双指针

不难想到，因为数组有序，设置左右指针，如果和大于目标值，右指针左移，如果和小于目标值，左指针右移，直到找到目标值。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
# Code language: Python
class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        n = len(nums)
        i, j = 1, n
        while i < j:
            s = nums[i - 1] + nums[j - 1]
            if s == target:
                return [i, j]
            elif s < target:
                i += 1
            else:
                j -= 1
        return [-1, -1]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
// Code language: Java
class Solution {
    public int[] twoSum(int[] nums, int target) {
        for (int i = 0, j = nums.length - 1; i < j;) {
            int s = nums[i] + nums[j];
            if (s < target)
                ++i;
            else if (s > target)
                --j;
            else
                return new int[] { i + 1, j + 1 };
        }
        return new int[] { -1, -1 };
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
// Code language: C++
class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        int n = nums.size();
        for (int i = 0, j = n - 1; i < j;) {
            int s = nums[i] + nums[j];
            if (s < target)
                ++i;
            else if (s > target)
                --j;
            else
                return vector<int>{i + 1, j + 1};
        }
        return vector<int>{-1, -1};
    }
};
  • 时间复杂度: \(O(n)\)
  • 空间复杂度: \(O(1)\)

双指针+二分查找

考虑到确定一个数后可以精确判断出需要的另外一个数，可以使用二分查找来确定另外一个数，即上面双指针移动指针部分使用二分查找。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
# Code language: Python
class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        """双指针 + 二分查找"""
        n = len(nums)
        i, j = 0, n - 1
        while i < j:
            s = nums[i] + nums[j]
            if s > target:
                left, right = i + 1, j - 1
                while left < right:
                    mid = left + right >> 1
                    ss = nums[i] + nums[mid]
                    if ss > target:
                        right = mid - 1
                    elif ss < target:
                        left = mid + 1
                    else:
                        return [i + 1, mid + 1]
                j = left
            elif s < target:
                left, right = i + 1, j - 1
                while left < right:
                    mid = left + right >> 1
                    ss = nums[mid] + nums[j]
                    if ss > target:
                        right = mid - 1
                    elif ss < target:
                        left = mid + 1
                    else:
                        return [mid + 1, j + 1]
                i = left
            else:
                return [i + 1, j + 1]
        return [-1, -1]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
// Code language: Java
class Solution {
    public int[] twoSum(int[] nums, int target) {
        for (int i = 0, j = nums.length - 1; i < j;) {
            int s = nums[i] + nums[j];
            if (s < target) {
                int left = i + 1, right = j - 1;
                while (left < right) {
                    int mid = left + right >> 1;
                    int sum = nums[mid] + nums[j];
                    if (sum < target)
                        left = mid + 1;
                    else if (sum > target)
                        right = mid - 1;
                    else
                        return new int[] { mid + 1, j + 1 };
                }
                i = left;
            }
            else if (s > target) {
                int left = i + 1, right = j - 1;
                while (left < right) {
                    int mid = left + right >> 1;
                    int sum = nums[i] + nums[mid];
                    if (sum < target)
                        left = mid + 1;
                    else if (sum > target)
                        right = mid - 1;
                    else
                        return new int[] { i + 1, mid + 1 };
                }
                j = left;
            }
            else
                return new int[] { i + 1, j + 1 };
        }
        return new int[] { -1, -1 };
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
// Code language: C++
class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        int n = nums.size();
        for (int i = 0, j = n - 1; i < j;) {
            int s = nums[i] + nums[j];
            if (s < target) {
                int left = i + 1, right = j - 1;
                while (left < right) {
                    int mid = left + right >> 1;
                    int sum = nums[mid] + nums[j];
                    if (sum < target)
                        left = mid + 1;
                    else if (sum > target)
                        right = mid - 1;
                    else
                        return vector<int>{mid + 1, j + 1};
                }
                i = left;
            }
            else if (s > target) {
                int left = i + 1, right = j - 1;
                while (left < right) {
                    int mid = left + right >> 1;
                    int sum = nums[i] + nums[mid];
                    if (sum < target)
                        left = mid + 1;
                    else if (sum > target)
                        right = mid - 1;
                    else
                        return vector<int>{i + 1, mid + 1};
                }
                j = left;
            }
            else
                return vector<int>{i + 1, j + 1};
        }
        return vector<int>{-1, -1};
    }
};
  • 时间复杂度: \(O(\log n)\)
  • 空间复杂度: \(O(1)\)

如果对你有帮助的话，请给我点个赞吧~

欢迎前往 我的博客 或 Algorithm - Github 查看更多题解

--- ♥ end ♥ ---

欢迎关注我呀~