LeetCode-18.四数之和 - sheep44044的小站

双指针#

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

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

示例 2：

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

1.自己的解法(双指针)

在三数之和的基础上加层循环即可，并处理下循环开始一些错误的剪枝，target可以为负，还是蛮需要三数之和的基础的

1
func fourSum(nums []int, target int) [][]int {
2
    var res [][]int
3
    n := len(nums)
4
    if n < 4 {
5
        return res
6
    }
7

8
    sort.Ints(nums)
9

10
    for i := 0; i < n-3; i++ {
11
        if i > 0 && nums[i] == nums[i-1] {
12
            continue
13
        }
14

15
        for j := i + 1; j < n-2; j++ {
16

17
            if j > i+1 && nums[j] == nums[j-1] {
18
                continue
19
            }
20

21
            left, right := j+1, n-1
22
            for left < right {
23
                sum := nums[i] + nums[j] + nums[left] + nums[right]
24
                if sum == target {
25
                    res = append(res, []int{nums[i], nums[j], nums[left], nums[right]})
26

27
                    for left < right && nums[left] == nums[left+1] {
28
                        left++
29
                    }
30

31
                    for left < right && nums[right] == nums[right-1] {
32
                        right--
33
                    }
34

35
                    left++
36
                    right--
37
                } else if sum < target {
38
                    left++
39
                } else {
40
                    right--
41
                }
42
            }
43
        }
44
    }
45
    return res
46
}