給定一個(gè)包含 n 個(gè)整數(shù)的數(shù)組 nums 和一個(gè)目標(biāo)值 target，判斷 nums 中是否存在四個(gè)元素 a，b，c 和 d ，使得 a + b + c + d 的值與 target 相等？找出所有滿足條件且不重復(fù)的四元組。

例如: 給定數(shù)組 nums = [1, 0, -1, 0, -2, 2]，和 target = 0。

滿足要求的四元組集合為：
[
[-1, 0, 0, 1],
[-2, -1, 1, 2],
[-2, 0, 0, 2]
]

因?yàn)槲覀冎翱催^三數(shù)之和: IOS 算法(中級(jí)篇) ----- 三數(shù)之和求解問題

仿照三數(shù)之和我們可以得到四數(shù)之和

雙指針

跟三數(shù)之和類似, 正序排列數(shù)組, 雙指針不斷收縮找值

    func fourSum(_ nums: [Int], _ target: Int) -> [[Int]] {

        //元素總數(shù)小于4, 直接返回
        if nums.count < 4 {
            return []
        }

        //數(shù)組正序排序
        let sort = nums.sorted(), length = sort.count
        //設(shè)置容器存放結(jié)果
        var result:[[Int]] = []
        
        //循環(huán), 最大設(shè)為length-3
        for i in 0..<length-3 {
            //過濾相同元素, 去重
            if i>0 && sort[i] == sort[i-1] {
                continue
            }
            //如果正序數(shù)組連續(xù)4個(gè)之和大于目標(biāo)target, 直接返回, 
           //原因: 正序數(shù)組, 后面相加更大
            if sort[i] + sort[i+1] + sort[i+2] + sort[i+3] > target {
                break;
            }
            //如果當(dāng)前元素和最大3個(gè)數(shù)之和小于目標(biāo)target, 直接進(jìn)行下一次循環(huán)
            //原因: 正序數(shù)組, 當(dāng)前元素加最大三個(gè)都小于目標(biāo), 可以繼續(xù)循環(huán)了
            if sort[i] + sort[length-3] + sort[length-2] + sort[length-1] < target {
                continue;
            }
            //循環(huán), 在 i+1~length-2, 找第二個(gè)數(shù)
            for j in i+1..<length-2 {
                
                //過濾相同元素, 去重
                if j>i+1 && sort[j] == sort[j-1] {
                    continue
                }
                //sort[i]與j循環(huán)前三個(gè)之和大于目標(biāo)直接break彈出
                if sort[i] + sort[j] + sort[j+1] + sort[j+2] > target {
                    break;
                }
                //sort[i], sort[j]與j循環(huán)最大兩個(gè)數(shù)之和小于目標(biāo), 直接進(jìn)行下一次循環(huán)
                if sort[i] + sort[j] + sort[sort.count-2] + sort[sort.count-1] < target {
                    continue;
                }
                //設(shè)置最小值下標(biāo), 最大值下標(biāo), 在這兩個(gè)區(qū)間內(nèi)找到我們想要的數(shù)
                var low = j + 1, high = length - 1
                //low, high 是不斷變化的
                while low < high {
                    //設(shè)置四數(shù)之和 sum
                    let sum: Int = sort[low] + sort[high] + sort[i] + sort[j]
                    
                    if sum == target {
                        //如果 sum = target, 容器添加
                        result.append([sort[low], sort[high], sort[j], sort[i]])
                        //去重
                        while low < high && sort[low] == sort[low + 1] {
                            low += 1

                        }
                        //去重
                        while low < high && sort[high] == sort[high - 1] {
                            high -= 1
                        }
                        //不斷收縮
                        low += 1
                        high -= 1

                    }else if sum < target{
                        //四數(shù)之和小于目標(biāo), low++
                        low += 1
                    }else {
                        //四數(shù)之和小于目標(biāo), high--
                        high -= 1
                    }
                }
            }
        }
        // 返回結(jié)果
        return result
    }

題目來源：力扣（LeetCode） 感謝力扣爸爸 :)
IOS 算法合集地址