技巧：快速求并集交集和差集

在做一个文件同步工具的时候，有这样一个需求：假设有source和target两个文件夹，确保两个文件夹中的文件一致。即当source中添加了新文件时，自动拷贝到target; 当source文件夹删除某个文件时，target中的文件也要删除。（实际上文件改动也要进行同步，但和这个例子没有关系）。这样就需要求两个集合的差集，这篇文章演示如何快速实现这一过程。

下面这幅图可以说明要执行的操作：

直观上，最容易想到的方法就是嵌套两个for循环来遍历这两个集合，但这样的时间复杂度是O(n^2)。一个更好的办法，是借助Hash表的快速访问能力来将嵌套的for循环改为单个的for循环。

下面是go语言的实现：

package main

import (
    "fmt"
    "strings"
)

func main() {
    source := []string{"apple", "banana", "pear", "watermelon", "strawberry"}
    target := []string{"pear", "watermelon", "strawberry", "orange", "litchi"}

    set := getSetDiff(source, target)
    all := []string{}  // 并集
    add := []string{}  // source和target的差集
    del := []string{}  // target和source的差集
    both := []string{} // 交集

    for k, v := range set {
        if v == 1 {
            add = append(add, k)
        }
        if v == 0 {
            both = append(both, k)
        }
        if v == -1 {
            del = append(del, k)
        }
        all = append(all, k)
    }

    fmt.Printf("并集: %v\n", strings.Join(all[:], ","))
    fmt.Printf("交集: %v\n", strings.Join(both[:], ","))
    fmt.Printf("source和target的差集: %v\n", strings.Join(add[:], ","))
    fmt.Printf("target和source的差集: %v\n", strings.Join(del[:], ","))
}

func getSetDiff(source, target []string) map[string]int {
    var m = make(map[string]int)

    for _, item := range source {
        m[item] = 1 // 差集 source-target
    }

    for _, item := range target {
        if _, ok := m[item]; ok {
            m[item] = 0 // source 和 target中都有的
        } else {
            m[item] = -1 // 差集 target-source
        }
    }

    return m
}

输出的结果如下：

并集: apple,banana,pear,watermelon,strawberry,orange,litchi
交集: pear,watermelon,strawberry
source和target的差集: apple,banana
target和source的差集: orange,litchi

在需要反复进行集合遍历的操作时，都可以考虑下是否有使用hash表的替代方案，使用hash表的速度往往要快很多，它存取数据的时间复杂度是：O(1)，而使用for循环对列表进行线性查找的时间复杂度是O(n)。

感谢阅读，希望这篇文章能给你带来帮助！