“不积跬步，无以至千里；不积小流，无以成江海”

算法的重要性我就不说了，不论是平时的项目中还是找工作的面试过程中，算法都是必不可少的，同时算法可以锻炼我们的思维逻辑能力以及解决问题的能力。
今天开始我就会从各类书籍以及博客等挑选出优质的算法题与大家分享，从简到难，在练习算法的同时，我也会对算法中运用的知识点进行整理，与大家共同学习成长，只要我们每天抽出半个小时到一个小时的时间去学习、整理、以及反思，我相信一段时间过后你会成长很多。

目录

1. 给出一个整形数组和一个目标值，判断数组中是否有两个数之和等于目标值。

2. 利用递归算法求1到n的和

3. 不借用第三个变量，如何交换两个变量的值？（变量a，b）

1. 给出一个整形数组和一个目标值，判断数组中是否有两个数之和等于目标值。

法一：很多人可能搭眼一看就能想到每次选中一个数，然后遍历整个数组判断有没有一个数相加之和等于目标值。但是这种方法的时间复杂度为O(n²)，太复杂，所以我们需要找到更好的方法优化时间复杂度。

法二：我们可以利用集合处理这次问题，在遍历数组的过程中，我们利用字典保存当前值，假如字典中存在一个数等于目标值减去当前值，那么可以证明整个遍历中一定有两个数之和等于目标值。你可以这种方法的时间复杂度为O(n)。

代码：

    func judgeTwoNums(numsArr: [Int], targetValue: Int) -> Bool {
        var set = Set<Int>()
        for num in numsArr {
            if set.contains(targetValue - num) {
               return true
            }
            set.insert(num)
            print("有两个数之和等于目标值")
        }
        return false
    }

拓展：

给定一个整形数组中有且仅有两个数之和等于目标值，求这两个数在数组中的序号。

此题的思路跟上面题的思路基本相似，不同之处是此题需要得到两个数在数组中的序号，所以不能使用集合(排列无序)来解决这个问题，为了方便得到序列号，我们使用字典来解决这个问题。时间的复杂度为O(n)。

    func judgeTwoNum(numsArr: [Int], targetValue: Int) -> [Int] {
        var dict = [Int: Int]()
        for (i, num) in numsArr.enumerated() {
            if let index = dict[targetValue - num] {
                return [index, i]
            } else {
                dict[num] = i
            }
        }
        return []
    }

知识点：

集合(set)：用来存储没有固定顺序、类型相同且不重复的值。

2. 利用递归算法求1到n的和

所谓递归，简单点来说，就是一个函数直接或间接调用自身的一种方法，它通常把一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解。

    //    MARK: 递归算法
    func sum(n: Int) -> Int {
        var result: Int
        if n == 0 {
            return 0
        } else if n == 1 {
            return 1
        } else {
            result = sum(n: (n - 1)) + n
            return result
        }
    }

3. 不借用第三个变量，如何交换两个变量的值？（变量a，b）

法一：

a = a + b
b = a- b --> b = (a + b) - b --> b = a
a= a- b --> a = (a + b) - b(此时b=a) --> a = b

a = a - b
b = a + b --> (a - b) + b --> b = a
a = a + b --> (a - b) + b(此时b=a) --> a= b

法二（按位异或）：
参加运算的两个数，换算为二进制(0、1)后，进行异或运算。只有当相应位上的数字不相同时，该为才取1，若相同，即为0。任何数与0异或，结果都是其本身。

a = a ^ b
b = b ^ a 
a = a ^ b