跳转至

两数之和Ⅱ-输入有序数组

最后更新：2024-05-09-22

链接：https://leetcode.cn/problems/two-sum-ii-input-array-is-sorted/description/

题目描述

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

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

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

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

题目示例

输入： numbers = [2,7,11,15], target = 9

输出： [1,2]

解释： 2 与 7 之和等于目标数 9 。因此 index1 = 1, index2 = 2 。返回 [1, 2]。

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

输出： [1,3]

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

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

输出： [1,2]

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

提示：

  • \(2 <= nums.length <= 3*10^4\)
  • \(-1000 <= nums[i] <= 1000\)
  • \(-1000 <= target <= 1000\)
  • numbers 按 非递减顺序 排列
  • 只会存在一个有效答案
Go
 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
type TwoSum struct {
    nums   []int
    target int
}

func Constructor() TwoSum {
    return TwoSum{
	    nums:   make([]int, 0),
	    target: 0,
    }
}

func (this *TwoSum) Add(number int) {
    this.nums = append(this.nums, number)
}

func (this *TwoSum) Find(value int) bool {
    sort.Ints(this.nums)
    left, right := 0, len(this.nums)-1
    for left < right {
	    sum := this.nums[left] + this.nums[right]
	    if sum == value {
		    return true
	    } else if sum < value {
		    left++
	    } else {
		    right--
	    }
    }
    
    return false
}