18.四数之和.md

18. 四数之和

题目描述

给你一个由 n 个整数组成的数组 nums ，和一个目标值 target 。请你找出并返回满足下述全部条件且不重复的四元组 [nums[a], nums[b], nums[c], nums[d]] （若两个四元组元素一一对应，则认为两个四元组重复）：

0 <= a, b, c, d < n a、b、c 和 d 互不相同 nums[a] + nums[b] + nums[c] + nums[d] == target 你可以按 任意顺序 返回答案 。

示例 1：

输入：nums = [1,0,-1,0,-2,2], target = 0 输出：[[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]] 示例 2：

输入：nums = [2,2,2,2,2], target = 8 输出：[[2,2,2,2]]

来源：力扣（LeetCode） 链接：https://leetcode.cn/problems/4sum

解题思路

这道题和15.三数之和解题思路相同，不过是在最外层加了一层循环， 用四指针来解决该问题

• one当前的基数
• two三数之和中的基数
• three两数之和的最小值索引
• four两数之和的最大值索引
  • one进行遍历
    • 确定one之后相当三数之和进行求解

代码如下

func fourSum(nums []int, target int) [][]int {
    if len(nums) < 4 {
        return [][]int{}
    }

    sort.Ints(nums)

    result := [][]int{}
    for one:=0; one < len(nums)-3; one++ {
        //去重
        if one > 0 && nums[one] == nums[one-1] {
            continue
        } 
        if (nums[one] + nums[one+1] + nums[one+2] + nums[one+3]) > target { //当前最小的和都比target大  不用再找了 直接下一层查找
            continue
        }
        if (nums[one] + nums[len(nums)-1] + nums[len(nums)-2] + nums[len(nums)-3]) < target { //当前最大的和都比target小  不用再找了 直接下一层查找
            continue
        }
        //两数之和逻辑
        for two := one+1; two < len(nums)-2; two++ {
            if two > one+1 && nums[two-1] == nums[two] { //和前一个数相同 去重
                continue
            }
            if (nums[one] + nums[two] + nums[two+1] + nums[two+2]) > target { //当前最小的和都比target大  不用再找了 直接下一层查找
                continue
            }
            if (nums[one] + nums[two] + nums[len(nums)-1] + nums[len(nums)-2]) < target { //当前最大的和都比target小  不用再找了 直接下一层查找
                continue
            }
            three, four := two+1, len(nums)-1
            for three < four {
                oneVal, twoVal, threeVal, fourVal := nums[one], nums[two], nums[three], nums[four]
                curSum := oneVal + twoVal + threeVal + fourVal
                if curSum == target {
                    result = append(result, []int{oneVal, twoVal, threeVal, fourVal})
                    fmt.Println(one,two, three,four)
                    three++
                    for three < four && nums[three] == threeVal {
                        three++
                    }
                    four--
                    for three < four && nums[four] == fourVal {
                        four--
                    }
                } else if curSum > target {
                    four--
                } else {
                    three++
                }
            }
        } 
    }
    return result
}

参考

• 优秀题解代码