题目名称

给你一个由 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

你可以按 任意顺序 返回答案 。

示例

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

输出：[[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]

题解

这道题和 第十二天做的 三数之和 运算步骤类似，可以参照逻辑。

答案

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
 var fourSum = function(nums, target) {
    if(nums.length === 4) {
        if(nums.reduce((total, item) => total += item) === target) {
            return [nums]
        } else {
            return []
        }
    }
    nums = nums.sort((a,b) => a-b)
    const arrHash = {}, arr = []
    for(let i = 0; i < nums.length - 3; i++) {
        let a = nums[i]
        for(let j = i+1; j < nums.length - 2; j++) {
            let b = nums[j]
            let l = j + 1, r =  nums.length - 1
            while(l < r) {
                const array = [a, b, nums[l], nums[r]]
                let total = a + b + nums[l] + nums[r]
                if(total > target) {
                    r--
                } else if(total < target) {
                    l++
                } else {
                    const str = array.join(",")
                    if(!arrHash[str]) {
                        arr.push(array)
                        arrHash[str] = true
                    }
                    r--
                    l++
                }
            }
        }
    }
    return arr
};