LeetCode 18: 4Sum
题目链接：
https://leetcode.cn/problems/4sum/
解题思路：
使用双指针算法来解决四数之和问题时，我们需要使用四个指针i、j、k和l。以下是一个简单的图示，为了更好地理解这个过程，起始示例图如下：
1
2
3
| i j k l
| | | |
[ 1, 2, 3, 4, 5, 6, 7, 8 ]
|
- 首先，我们让i指向数组的第一个元素，j指向i后面的第一个元素，k指向j后面的第一个元素，l指向数组的最后一个元素。
- 然后，我们开始枚举所有可能的四元组。对于每个四元组，我们计算它们的和sum，并比较sum和目标值target的大小关系。
- 如果sum小于target，说明我们需要增加四元组的和，因此将k指针向右移动一位，以便选择一个更大的数。
- 如果sum大于target，说明我们需要减少四元组的和，因此将l指针向左移动一位，以便选择一个更小的数。
- 如果sum等于target，说明我们找到了一个满足条件的四元组，将其添加到结果集中，并将k和l指针向内移动一位，以便继续寻找下一个四元组。
- 在处理完当前四元组后，我们还需要检查j和k之间是否存在重复元素，以及k和l之间是否存在重复元素，如果存在，则需要跳过这些重复元素。
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
| func fourSum(_ nums: [Int], _ target: Int) -> [[Int]] {
guard nums.count > 3 else {
return []
}
var solutions = [[Int]]()
let sorted = nums.sorted() { $0 < $1 }
let count = sorted.count
let minSum = sorted[0] + sorted[1] + sorted[2] + sorted[3]
let maxSum = sorted[count - 1] + sorted[count - 2] + sorted[count - 3] + sorted[count - 4]
if target < minSum {
return solutions
}
if target > maxSum {
return solutions
}
print(sorted)
for i in 0..<(nums.count - 3) {
if i > 0 && sorted[i] == sorted[i - 1] {continue}
for j in (i + 1)..<(nums.count - 2) {
if j > i + 1 && sorted[j] == sorted[j - 1] {continue}
var k = j + 1
var l = nums.count - 1
let twoSumTarget = target - sorted[i] - sorted[j]
while k < l {
let twoSum = sorted[k] + sorted[l]
if twoSum < twoSumTarget {k += 1}
if twoSum > twoSumTarget {l -= 1}
if twoSum == twoSumTarget {
solutions.append([sorted[i], sorted[j], sorted[k], sorted[l]])
repeat {k += 1} while k < l && sorted[k] == sorted[k - 1]
repeat {l -= 1} while k < l && sorted[l] == sorted[l + 1]
}
}
}
}
return solutions
}
|