题目：
知识点：双指针
题目描述
输入一个递增排序的数组和一个数字S，在数组中查找两个数，使得他们的和正好是S，如果有多对数字的和等于S，输出两个数的乘积最小的。
输出描述:
对应每个测试案例，输出两个数，小的先输出。
自己的做法
- 一看此题两个for循环，但是显然没有运用到 已经排序, 虽然通过但是复杂度太高
class Solution:
def FindNumbersWithSum(self, array, tsum):
# write code here
res = []
for i in range(len(array)-1):
for j in range(len(array)):
if array[i] + array[j] == tsum:
if not res:
res = [array[i],array[j]]
elif array[i]*array[j] < res[0]*res[1]:
res = [array[i],array[j]]
return res
参考进阶
思路
- 递增（有序）： 想到 二分类，指针（左右移动）
- 最小：两个数和一定，差越大积越小 （如，和一定，两条边越接近，面积越大），所以选择第一个就好
# -*- coding:utf-8 -*-
class Solution:
def FindNumbersWithSum(self, array, tsum):
# write code here
# 指针！！！
left = 0
right = len(array)-1
while left < right:
sum1 = array[left]+array[right]
if sum1 > tsum:
right -= 1
elif sum1 < tsum:
left += 1
else:
return[array[left], array[right]]
return []
~~初次编辑，如有不妥，多多指教评论，谢谢
~~记录，回顾
