cubegao

Swift.和为S的两个数字VS和为S的连续正数序列

2016-04-06

题目描述：
题目一：输入一个递增排序的数组和一个数字 s，在数组中查找两个数，得它们的和正好是 s。如果有多对数字的和等于 s，输出任意一对即可。
题目二：输入一个正数 s，打印出所有和为 s 的连续正数序列（至少两个数）。

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
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
import Foundation

class For41Solution {
    func sumIsK(_ nums: [Int],_ k: Int) {
        
        var left = 0
        var right = nums.count - 1
        
        while  left < right {
            
            if nums[right] + nums[left] == k {
                print("\(nums[right])+\(nums[left])=\(k)")
                return
            }else if nums[right] + nums[left] > k {
                right -= 1
            }else {
                left += 1
            }
        }
        
        print("no result!")
    }
    
    
    func sumsIsKSqeuence(_ k: Int) {
        
        if k < 3 {
            return
        }
        
        var small = 1
        var big = 2
        let mid = (1 + k)/2
        var sums = small + big
        
        
        //最少要2个数
        while small < mid {
            
            if sums == k {
                forKPrint(small, big)
            }
            
            while small < mid && sums < k {
                big += 1
                sums += big
                
                if sums == k {
                    forKPrint(small, big)
                }
            }
            
            sums -= small
            small += 1
        }
        
        print("is all!")
        
    }
    
    func forKPrint(_ small: Int,_ big: Int) {
        
        for i in small..<big+1 {
            print(i)
        }
        
        print("once!")

    }
}

算法思想：
题目一：我们先在数组中选择两个数字，如果它们的和等于输入的 s，我们就找到了要找的两个数字。如果和小于 s 呢？我们希望两个数字的和再大一点。由于数组已经排好序了，我们可以考虑选择较小的数字后面的数字。因为排在后面的数字要大一些，那么两个数字的和也要大一些， 就有可能等于输入的数字 s 了。同样， 当两个数字的和大于输入的数字的时候，我们可以选择较大数字前面的数字，因为排在数组前面的数字要小一些。
题目二：考虑用两个数 small 和 big 分别表示序列的最小值和最大值。首先把 small 初始化为 1，big 初始化为 2。如果从 small 到 big 的序列的和大于 s，我们可以从序列中去掉较小的值，也就是增大 small 的值。如果从 small 到 big 的序列的和小于 s，我们可以增大 big，让这个序列包含更多的数字。因为这个序列至少要有两个数字，我们一直增加 small 到(1+s)/2 为止。

这类题有个共性，就是两个指针，一前一后。

github地址：https://github.com/cubegao/LeetCode

Tags: 算法
← Swift.两个链表的第一个公共结点 Swift.二叉树的深度 →

扫描二维码，分享此文章