LeetCode算法题-18. 四数之和（Swift）

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/4sum
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

题目

给定一个包含 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]
]

数组排序
外面一个for循环，a的index，之后一个一个加。
b的index初始是count-1。之后再一个一个减去。
c和d是在一个while循环中，通过两个指针同时来找，一个是firstIndex+1，一个是lastIndex-1。

方法

  func fourSum(_ nums: [Int], _ target: Int) -> [[Int]] {
        
        //如果数组count<4，直接return[]
        if nums.count < 4 {
            return []
        }
        //数组排序
        let sortedNums = nums.sorted()
        //如果数组最小值*4>target，直接return[]
        if sortedNums[0] * 4 > target {
            return []
        }

        var resultArr:Array = [[Int]]()
        
        //a的index，用for循环遍历确认第一个值是哪个
        var firstIndex = 0 //第一个值的index
        for i in 0...nums.count - 4 {
            
            firstIndex = i
            //判断a的值是否和上个重复
            if firstIndex != 0 && sortedNums[firstIndex - 1] == sortedNums[firstIndex] {
                firstIndex += 1
                if firstIndex > nums.count - 4 {
                    break
                }
                continue
            }
            
            let a = sortedNums[firstIndex]

            var lastIndex = nums.count - 1 //b的index，初始坐最后开始index
            //a和b之间隔着c和d两个数
            while lastIndex - firstIndex >= 2 {
                
                let b = sortedNums[lastIndex]

                //c和d是在a和b之间，一个从头开始找，一个从尾开始找。
                var secondIndex = firstIndex + 1
                var thirdIndex = lastIndex - 1
                
                var c = 0
                var d = 0

                
                while secondIndex < thirdIndex {
                    
                    c = sortedNums[secondIndex]
                    d = sortedNums[thirdIndex]
                    
                    if a+b+c+d == target {
                        resultArr.append([a,b,c,d])
                        secondIndex += 1
                        thirdIndex -= 1
                        
                        while c == sortedNums[secondIndex] && d == sortedNums[thirdIndex] && secondIndex < thirdIndex{
                            secondIndex += 1
                            thirdIndex -= 1
                        }
                    }else if a+b+c+d < target {
                        secondIndex += 1
                        while c == sortedNums[secondIndex] && secondIndex < thirdIndex {
                            secondIndex += 1
                        }
                    }else {
                        thirdIndex -= 1
                        while d == sortedNums[thirdIndex] && secondIndex < thirdIndex {
                            thirdIndex -= 1
                        }
                    }
                }
                
                lastIndex -= 1
                //判断b的值是否和上个重复
                while lastIndex != nums.count - 1 && sortedNums[lastIndex + 1] == sortedNums[lastIndex] && lastIndex - firstIndex >= 2 {
                    lastIndex -= 1
                }
            }
        }
        
        resultArr = resultArr.map({$0.sorted()})
        var result = [[Int]]()
        
        for array in resultArr {
            
            if !result.contains(array) {
                result.append(array)
            }
        }
        return result
        
    }