目录

和为s的两个数字
和为s的连续正数序列

和为s的两个数字

输入一个递增排序的数组和一个数字s，在数组中查找两个数，使得它们的和正好是s。
如果有多对的数字的和等于s，则输出任意一对即可。
样例：

输入：数组{1,2,4,7,11,15}和数字15
输出：4和11
1
2

解题思路

首先可以想到$O(n^2)$的做法：固定一个元素，判断剩下的n-1个和这个元素相加是否等于s. 这种解法显然忽略了递增排序这一个特点。
想想更好的算法，我们可以在数组中先选择两个数字，如果两数之和大于s，我们就希望两个数字可以小一点。再结合递增排序，就可以得出$O(n)$的解法。

双指针

• 我们定义一头一尾两个指针，然后让两数之和与s作比较；
• 如果两数和比s大，尾指针往前一位，否则头指针往后一位；
• 如果两数和恰好为s时，返回两个数字。

class Solution:
    def FindNumbersWithSum(self, array, tsum):
        # write code here
        if not array:
            return []
        first = 0
        last = len(array)-1
        res = []
        while first < last:
            if array[first] + array[last] == tsum:
                res.append([array[first], array[last]])
                first += 1
                last -= 1
            elif array[first] + array[last] < tsum:
                first += 1
            else:
                last -= 1
        
        # 牛客网上要求返回乘积最小的一对，因此要做比较
        if res:
            index = 0
            product = res[0][0] * res[0][1]
            for i in range(len(res)):
                if res[i][0] * res[i][1] <= product:
                    product = res[i][0] * res[i][1]
                    index = i
            return res[index]
         
        return []
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

和为s的连续正数序列

输入一个正数s，打印出所有和为s的连续正数序列（至少含有两个数）。
样例：

输入：15
输入：[[1,2,3,4,5],[4,5,6],[7,8]]
1
2

解题思路

沿用上一题的思路：

• 如果当前序列和比s大，就可以去掉较小的元素；
• 若当前序列和比s小，可以加上较大的元素。

双指针

• 定义两个指针small,big分别表示序列的最小值和最大值，并初始化为1和2；
• 当序列和大于s时，增大small的值，相当于去掉了序列中较小的元素；
• 当序列和小于s时，增大big的值，相当于加上了后续较大的元素。

class Solution:
    def FindContinuousSequence(self, tsum):
        # write code here
        if tsum < 3: return []
        
        small = 1
        big = 2
        res = []
        
        while small < big:
            temp_sum = ( small+big ) * (big - small + 1) / 2
            if temp_sum == tsum:
            	# 注意range的范围不要写错
                res.append(list(range(small,big+1)))
                small += 1
            elif temp_sum > tsum:
                small += 1
            else:
                big += 1
         
        return res
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21