18. 四数之和

想到的dfs。。 内存也不占优势，速度也不占优势= =。还好没超时

func fourSum(_ nums: [Int], _ target: Int) -> [[Int]] {
        var sum = 0
        let len =  nums.count
        let sortNums = nums.sorted()
        var tempArray = Array.init(repeating: 0, count: 4)
        var ans = [[Int]]()
        dfs(0,0,target,&sum,len,sortNums,&tempArray,&ans)

      return ans
    
    }
    
    func dfs(_ index:Int, _ begin:Int,_ target:Int,_ sum:inout Int,_ len: Int,_ sortNums:[Int],_ tempArray:inout [Int],_ ans: inout [[Int]]){
        
        if index == 4 {
            if sum == target {
                ans.append(tempArray)
            }
            
            return
        }
        
        for i in begin..<len {
            
            let num = sortNums[i]
            if i > begin && num == sortNums[i - 1] {
                continue
            }
            tempArray[index] = num
            sum += num
            dfs(index + 1, i + 1,target,&sum,len,sortNums,&tempArray,&ans)
            sum -= num
        }

    }

仿照三数之和。。

func fourSum(_ nums: [Int], _ target: Int) -> [[Int]] {
        let len =  nums.count
        if len < 4 {
            return []
        }
        let sortNums = nums.sorted()        
        var ans = [[Int]]()
        var index2 = 0, index3 = 0 ,index4 = 0
        let indexLast = len - 4
        let index2Last = len - 3
//        let index3Last = len - 2
        let index4Last = len - 1
        for i in 0...indexLast{
            index2 = i + 1
            let num1 = sortNums[i]
//            //过滤掉第一层重复的数字
            if i > 0 && num1 == sortNums[i - 1] {
                continue
            }
            
            
            for j in index2...index2Last {
                let num2 = sortNums[j]
 
                index3 = j + 1
                //过滤第二层重复的
                if j > index2 && num2 == sortNums[j - 1] {
                    continue
                }
                index4 = index4Last
                while index3 < index4 {
                    let num3 = sortNums[index3]
                    let num4 = sortNums[index4]
                    let sum = num1 + num2 + num3 + num4
                    //遇到符合条件的
                    if sum == target {
                        ans.append([num1,num2,num3,num4])
                            while index3 < index4 && num3 == sortNums[index3 + 1] {
                                index3 += 1
                                continue
                            }
                            while index3 < index4 && num4 == sortNums[index4 - 1] {
                                index4 -= 1
                                continue
                            }
                        index3 += 1
                        index4 -= 1

                    }else if sum < target {
                        index3 += 1
                    }else {
                        index4 -= 1
                    }


                }
    
                
   
            }
   
        }
    
      return ans
    
    }

然后优化版本，当排序之后。。最小的都大于target的时候 就可以不用往下走了。。因为后边的组合只会更大

func fourSum(_ nums: [Int], _ target: Int) -> [[Int]] {
        let len =  nums.count
        if len < 4 {
            return []
        }
        let sortNums = nums.sorted()        
        var ans = [[Int]]()
        var index2 = 0, index3 = 0 ,index4 = 0
        let indexLast = len - 4
        let index2Last = len - 3
        let index4Last = len - 1
        for i in 0...indexLast{
            index2 = i + 1
            let num1 = sortNums[i]
//            //过滤掉第一层重复的数字
            if i > 0 && num1 == sortNums[i - 1] {
                continue
            }
            if num1 + sortNums[i + 1] + sortNums[i + 2] + sortNums[i + 3] > target {
                break
            }
            
            for j in index2...index2Last {
                let num2 = sortNums[j]
 
                index3 = j + 1
                //过滤第二层重复的
                if j > index2 && num2 == sortNums[j - 1] {
                    continue
                }
                if num1 + num2 + sortNums[j + 1] + sortNums[j + 2] > target {
                    break
                }
                index4 = index4Last
                while index3 < index4 {
                    let num3 = sortNums[index3]
                    let num4 = sortNums[index4]
                    let sum = num1 + num2 + num3 + num4
                    //遇到符合条件的
                    if sum == target {
                        ans.append([num1,num2,num3,num4])
                            while index3 < index4 && num3 == sortNums[index3 + 1] {
                                index3 += 1
                                continue
                            }
                            while index3 < index4 && num4 == sortNums[index4 - 1] {
                                index4 -= 1
                                continue
                            }
                        index3 += 1
                        index4 -= 1

                    }else if sum < target {
                        index3 += 1
                    }else {
                        index4 -= 1
                    }


                }
    
                
   
            }
   
        }
    
      return ans
    
    }