IOS 算法(中级篇) ----- 四数之和求解问题

给定一个包含 n 个整数的数组 nums 和一个目标值 target，判断 nums 中是否存在四个元素 a，b，c 和 d ，使得 a + b + c + d 的值与 target 相等？找出所有满足条件且不重复的四元组。

例如: 给定数组 nums = [1, 0, -1, 0, -2, 2]，和 target = 0。

满足要求的四元组集合为：
[
[-1, 0, 0, 1],
[-2, -1, 1, 2],
[-2, 0, 0, 2]
]

因为我们之前看过三数之和: IOS 算法(中级篇) ----- 三数之和求解问题

仿照三数之和我们可以得到四数之和

双指针

跟三数之和类似, 正序排列数组, 双指针不断收缩找值

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

        //元素总数小于4, 直接返回
        if nums.count < 4 {
            return []
        }

        //数组正序排序
        let sort = nums.sorted(), length = sort.count
        //设置容器存放结果
        var result:[[Int]] = []
        
        //循环, 最大设为length-3
        for i in 0..<length-3 {
            //过滤相同元素, 去重
            if i>0 && sort[i] == sort[i-1] {
                continue
            }
            //如果正序数组连续4个之和大于目标target, 直接返回, 
           //原因: 正序数组, 后面相加更大
            if sort[i] + sort[i+1] + sort[i+2] + sort[i+3] > target {
                break;
            }
            //如果当前元素和最大3个数之和小于目标target, 直接进行下一次循环
            //原因: 正序数组, 当前元素加最大三个都小于目标, 可以继续循环了
            if sort[i] + sort[length-3] + sort[length-2] + sort[length-1] < target {
                continue;
            }
            //循环, 在 i+1~length-2, 找第二个数
            for j in i+1..<length-2 {
                
                //过滤相同元素, 去重
                if j>i+1 && sort[j] == sort[j-1] {
                    continue
                }
                //sort[i]与j循环前三个之和大于目标直接break弹出
                if sort[i] + sort[j] + sort[j+1] + sort[j+2] > target {
                    break;
                }
                //sort[i], sort[j]与j循环最大两个数之和小于目标, 直接进行下一次循环
                if sort[i] + sort[j] + sort[sort.count-2] + sort[sort.count-1] < target {
                    continue;
                }
                //设置最小值下标, 最大值下标, 在这两个区间内找到我们想要的数
                var low = j + 1, high = length - 1
                //low, high 是不断变化的
                while low < high {
                    //设置四数之和 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{
                        //四数之和小于目标, low++
                        low += 1
                    }else {
                        //四数之和小于目标, high--
                        high -= 1
                    }
                }
            }
        }
        // 返回结果
        return result
    }

题目来源：力扣（LeetCode） 感谢力扣爸爸 :)
IOS 算法合集地址