跳转至

四数之和

最后更新：2024-05-09-22

链接：https://leetcode.cn/problems/3sum/description/

题目描述

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

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

输出： [[2,2,2,2]]

提示：

  • \(1 <= nums.length <= 200\)
  • \(-10^9 <= nums[i] <= 10^9\)
  • \(-10^9 <= target <= 10^9\)
Go
 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
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
type fourSumData struct {
    nums                         []int
    n, target                    int
    res                          [][]int
    first, second, third, fourth int
}

func (t *fourSumData) fourSumWithFixC() {
    nums := t.nums
    n := t.n
    // 双指针
    for left, right := t.second+1, n-1; left < right; {
	    if sum := nums[t.first] + nums[t.second] + nums[left] + nums[right]; sum == t.target {
		    t.res = append(t.res, []int{nums[t.first], nums[t.second], nums[left], nums[right]})
		    for left++; left < right && nums[left] == nums[left-1]; left++ {
		    }
		    for right--; left < right && nums[right] == nums[right+1]; right-- {
		    }
	    } else if sum < t.target {
		    left++
	    } else {
		    right--
	    }
    }
}

func (t *fourSumData) fourSumWithFixB() {
    nums := t.nums
    n := t.n
    for second := t.first + 1; second < n-2; second++ {
	    // 连续的四个值，和大于target时，则四元组肯定不满足条件
	    if nums[t.first]+nums[second]+nums[second+1]+nums[second+2] > t.target {
		    return
	    }
	    // a、b、c 和 d 互不相同，如果相同，或者 A+B+最大的两个值，不满足条件，则以当前值为a值，不会再有满足条件的四元组
	    if second > t.first+1 && nums[second] == nums[second-1] || nums[t.first]+nums[second]+nums[n-2]+nums[n-1] < t.target {
		    continue
	    }
	    t.second = second
	    t.fourSumWithFixC()
    }
}

func (t *fourSumData) fourSumWithFixA() {
    nums := t.nums
    sort.Ints(t.nums)
    n := t.n
    for first := 0; first < n-3; first++ {
	    // 连续的四个值，和大于target时，则四元组肯定不满足条件
	    if nums[first]+nums[first+1]+nums[first+2]+nums[first+3] > t.target {
		    return
	    }

	    // a、b、c 和 d 互不相同，如果相同，或者A+最大的三个值，不满足条件，则以当前值为a值，不会再有满足条件的四元组
	    if first > 0 && nums[first] == nums[first-1] || nums[first]+nums[n-3]+nums[n-2]+nums[n-1] < t.target {
		    continue
	    }

	    t.first = first
	    t.fourSumWithFixB()
    }

    return
}

func fourSum(nums []int, target int) [][]int {
    data := &fourSumData{
	    nums:   nums,
	    n:      len(nums),
	    target: target,
	    res:    make([][]int, 0),
    }
    data.fourSumWithFixA()
    return data.res
}