arrays - 查找总和等于给定总和的所有唯一对

Question

我想找到所有总和等于给定总和的唯一对。我实现了一个解决方案，但它只返回它找到的第一对。

func checkPairs(in numbers: [Int], forSum target: Int) -> String {    
    for (i, x) in numbers.enumerated() {
        for y in numbers[i+1 ..< numbers.count] {
            if x + y == target {
                return ("There is a pair that sums \(target): \(x)+\(y)=\(target)")
            }
        }
    }
    return "no pair"
}

print (checkPairs(in: [1, 2, 4, 4, 7, 5, 3], forSum: 8))

输出:

There is a pair that sums 8: 1+7=8

Answer 1

当找到第一对时，您可以通过调用 return 提前退出该函数。相反，您应该返回一个包含对的元组数组，遍历所有对并将满足要求的对添加到返回数组。

func checkPairs(in numbers: [Int], forSum target: Int) -> [(Int,Int)] {
    var pairs = [(Int,Int)]()
    for (i, x) in numbers.enumerated() {
        for y in numbers[i+1 ..< numbers.count] {
            if x + y == target {
                pairs.append((x,y))
            }
        }
    }
    return pairs
}

print(checkPairs(in: [1, 2, 4, 4, 7, 5, 3], forSum: 8))

输出:

[(1, 7), (4, 4), (5, 3)]

如果您正在寻找独特的对，您可以定义一个自定义类型来保存这对数字并返回一个 Set 而不是 Array(自定义类型是需要，因为您不能使 Tuple 符合 Hashable，这是将元素添加到 Set 所必需的)。

struct Pair: Hashable {
    let smaller:Int
    let bigger:Int
    
    init(_ a:Int, _ b:Int) {
        if a < b {
            smaller = a
            bigger = b
        } else {
            smaller = b
            bigger = a
        }
    }
}

extension Pair: CustomStringConvertible {
    var description:String {
        return "\((smaller,bigger))"
    }
}

func checkPairs(in numbers: [Int], forSum target: Int) -> Set<Pair> {
    var pairs = Set<Pair>()
    for (i, x) in numbers.enumerated() {
        for y in numbers[i+1 ..< numbers.count] {
            if x + y == target {
                pairs.insert(Pair(x,y))
            }
        }
    }
    return pairs
}

print(checkPairs(in: [1, 2, 4, 4, 7, 5, 3], forSum: 8))
print(checkPairs(in: [1, 2, 4, 4, 7, 5, 3, 4, 1], forSum: 8))

输出:

[(4, 4), (3, 5), (1, 7)]

[(4, 4), (3, 5), (1, 7)]