和为S的两个数字
和为S的两个数字
http://www.nowcoder.com/questionTerminal/390da4f7a00f44bea7c2f3d19491311b
题目描述
输入一个递增排序的数组和一个数字S,在数组中查找两个数,使得他们的和正好是S,如果有多对数字的和等于S,输出两个数的乘积最小的。
刚开始看见题目第一反应就是用双指针,后来看见说要输出两个数的乘积最小的,这个时候就被题干迷惑了,初始化了一个二维数组,将每一对满足要求的数字添加到该二维数组中,可是越写感觉越不对劲,心里默默地想了一串数组,例如:[1,2,3,4,5,6,7,8]要求两数之和为9,按照我的双指针left指向第一个数,right指向最后一个数,会依次输出[1,8],[2,7],[3,6],[4,5]。很明显最小的就是输出的第一对,所以无需考虑题目中输出乘积最小的要求,碰见的第一对满足要求的,就是最小的!
思路:使用双指针,left指向数组第一个数,right指向最后一个数,初始化一个空列表result用来存放满足要求的两个数;
判断array[left]+array[right]与tsum的关系:若大于tsum,则将right指针左移;若小于tsum,则将left指针右移;若相等,则可以添加到result里,返回即可。
注意:相等添加完毕之后要使用break跳出循环,否则会出错,提示内存超过限制!
# -*- coding:utf-8 -*- class Solution: def FindNumbersWithSum(self, array, tsum): # write code here n = len(array) result = [] if array is None or n <= 1: return result left = 0 right = n - 1 while left < right: if array[left] + array[right] > tsum: right -= 1 elif array[left] + array[right] < tsum: left += 1 else: result.append(array[left]) result.append(array[right]) break //一定要使用break跳出循环 return result