难度: Easy
购物车内的商品价格按照升序记录于数组 price。请在购物车中找到两个商品的价格总和刚好是 target。若存在多种情况，返回任一结果即可。
示例 1：
输入：price = [3, 9, 12, 15], target = 18 输出：[3,15] 或者 [15,3]
示例 2：
输入：price = [8, 21, 27, 34, 52, 66], target = 61 输出：[27,34] 或者 [34,27]
提示：
1 <= price.length <= 10^51 <= price[i] <= 10^61 <= target <= 2*10^6运行时间: 116 ms
内存: 25.5 MB
from typing import List
class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
i = 0
j = len(nums) - 1
while i < j:
s = nums[i] + nums[j]
if s > target:
j -= 1
elif s < target:
i += 1
else:
return [nums[i], nums[j]]
if __name__ == '__main__':
s = Solution()
print(s.twoSum([2, 7, 11, 15], 9))
题解采用了双指针技巧，通过设置一个指针i指向数组的起始位置，另一个指针j指向数组的末尾位置。通过比较两个指针所指元素的和与目标值的关系来调整指针的位置：如果两数之和大于目标值，则将右侧指针向左移动以减小和的值；如果两数之和小于目标值，则将左侧指针向右移动以增大和的值；如果两数之和等于目标值，就返回这两个元素。由于数组是有序的，这种方法能有效地找到目标组合。
时间复杂度: O(n)
空间复杂度: O(1)
from typing import List
class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
i = 0 # 初始化左指针
j = len(nums) - 1 # 初始化右指针
while i < j: # 当左指针小于右指针时循环
s = nums[i] + nums[j] # 计算当前两指针指向值的和
if s > target: # 如果和大于目标值
j -= 1 # 移动右指针向左
elif s < target: # 如果和小于目标值
i += 1 # 移动左指针向右
else: # 如果和等于目标值
return [nums[i], nums[j]] # 返回结果
if __name__ == '__main__':
s = Solution()
print(s.twoSum([2, 7, 11, 15], 9)) # 示例调用和输出
在已排序的数组中，双指针从两端开始移动可以有效地利用数组的有序性确定指针的移动方向。一个指针从左端开始，代表最小值区域，另一个从右端开始，代表最大值区域。如果两指针指向值的和小于目标值，说明需要增大和的值，因此移动左侧指针向右以获取一个更大的数；如果和大于目标值，需要减小和的值，因此移动右侧指针向左以获取一个更小的数。如果数组未排序，这样的移动就无法保证正确调整和的大小，因为移动任一指针的结果对和的影响是不确定的。
在这种算法中，当i和j指向同一元素时，即nums[i] == nums[j]，实际上是不可能的，因为算法的循环条件是i < j，即两指针不会指向同一位置。因此，如果目标值target等于nums[i]*2，只有当数组中存在两个相同的值时，这两个值分别被i和j指向才能正确返回。如果数组中没有重复的符合条件的元素，或者没有两个不同位置的元素其值乘以2等于target，则算法不会找到这样的一对数。
在已排序的数组中，这种操作不会错过正确的组合。因为当和大于目标值时，为了减小和的值，必须减少当前的和。在数组已排序的情况下，右指针向左移动意味着取一个较小的数，从而减小和的总值。如果向左移动右指针而错过了正确的组合，那意味着存在比当前右指针还要大的数与左指针指向的数相加等于目标值，这与数组排序的性质相矛盾。
是的，这种边界情况已经被正确处理。当数组仅有两个元素时，i初始化为0，j初始化为1，即i和j分别指向这两个元素。因为条件i < j成立，循环会执行。在循环内部，如果这两个元素的和等于目标值，那么这对元素将被返回。因此，即使是只有两个元素的数组，只要它们的和符合目标值，算法也能正确返回这两个元素。