Skip to content

Commit f0c7874

Browse files
author
luzhicheng
committed
四数之和
四数之和
1 parent 3386dd3 commit f0c7874

4 files changed

Lines changed: 136 additions & 0 deletions

File tree

‎leetcode_array/main.md‎

Lines changed: 2 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -11,6 +11,8 @@
1111
* [移除元素(快慢指针)](移除元素.md)
1212
* [长度最小的子数组(滑动窗口)](长度最小的子数组.md)
1313
* [螺旋矩阵II](螺旋矩阵2.md)
14+
* [三数之和(左右指针)](三数之和.md)
15+
* [四数之和](四数之和.md)
1416

1517
<!--
1618
2. [删除排序数组中的重复项](删除排序数组中的重复项.md)

‎leetcode_array/三数之和.md‎

Lines changed: 69 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,69 @@
1+
# 15.三数之和
2+
## 题目
3+
给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有和为 0 且不重复的三元组。
4+
5+
注意：答案中不可以包含重复的三元组。
6+
7+
```python
8+
输入：nums = [-1,0,1,2,-1,-4]
9+
输出：[[-1,-1,2],[-1,0,1]]
10+
11+
输入：nums = []
12+
输出：[]
13+
14+
输入：nums = [0]
15+
输出：[]
16+
```
17+
18+
## 分析
19+
![](../pic/leetcode_array/15_1.gif)
20+
21+
* 长度小于3的数组直接返回[]
22+
* 对数组排序
23+
* 遍历排序后的数组
24+
* 若nums[i]>0：因为已经排序好，所以后面不可能有三个数加和等于0，直接返回结果
25+
* 对于重复元素：跳过，避免出现重复解
26+
* 令左指针L=i+1，右指针R=n−1，当 L<R 时，执行循环：
27+
* 当nums[i]+nums[L]+nums[R]==0，执行循环，判断左界和右界是否和下一位置重复，去除重复解。并同时将 L,R 移到下一位置，寻找新的解
28+
* 若和大于 0，说明 nums[R] 太大，R左移
29+
* 若和小于 0，说明 nums[L] 太小，L右移
30+
* 时间复杂度O(n^2),外层for循环遍历数组，内层双指针遍历数组
31+
32+
```python
33+
class Solution:
34+
def threeSum(self, nums: List[int]) -> List[List[int]]:
35+
length = len(nums)
36+
if length < 3:
37+
return []
38+
nums.sort()
39+
ans = []
40+
for i in range(length):
41+
if nums[i] > 0:
42+
# 排序后的数组如果第一个元素都大于0，那三数之和必然大于0
43+
continue
44+
45+
if i > 0 and nums[i] == nums[i-1]:
46+
# 跳过重复元素
47+
continue
48+
49+
L = i+1
50+
R = length-1
51+
while L < R:
52+
sum_ = nums[i] + nums[L] + nums[R]
53+
if sum_ < 0:
54+
L += 1
55+
continue
56+
elif sum_ > 0:
57+
R -= 1
58+
continue
59+
else:
60+
ans.append([nums[i], nums[L], nums[R]])
61+
L += 1
62+
R -= 1
63+
while L < R and nums[L] == nums[L-1]:
64+
L += 1
65+
while L < R and nums[R] == nums[R+1]:
66+
R -= 1
67+
68+
return ans
69+
```

‎leetcode_array/四数之和.md‎

Lines changed: 65 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,65 @@
1+
# 18.四数之和
2+
给定一个包含 n 个整数的数组 nums 和一个目标值 target，判断 nums 中是否存在四个元素 a，b，c 和 d ，使得 a + b + c + d 的值与 target 相等？找出所有满足条件且不重复的四元组。
3+
4+
注意：答案中不可以包含重复的四元组。
5+
```python
6+
输入：nums = [1,0,-1,0,-2,2], target = 0
7+
输出：[[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]
8+
9+
输入：nums = [], target = 0
10+
输出：[]
11+
```
12+
13+
## 分析
14+
思路与[三数之和](三数之和.md)一样，比三数之和多了一层循环。时间复杂度O(n^3)
15+
16+
```python
17+
def fourSum(nums, target):
18+
length = len(nums)
19+
if length < 4:
20+
return []
21+
nums.sort()
22+
ans = []
23+
for i in range(length-3):
24+
if i > 0 and nums[i-1] == nums[i]:
25+
continue
26+
27+
# 优化效率，去掉没必要的循环
28+
if nums[i] + nums[i+1] + nums[i+2] + nums[i+3] > target:
29+
# 排序后前四位大于目标值可以直接退出
30+
break
31+
if nums[i] + nums[length-3] + nums[length-2] + nums[length-1] < target:
32+
continue
33+
34+
for j in range(i+1, length-2):
35+
if j > i+1 and nums[j-1] == nums[j]:
36+
continue
37+
38+
# 优化效率，去掉没必要的循环
39+
if nums[i] + nums[j] + nums[j+1] + nums[j+2] > target:
40+
# 排序后前四位大于目标值可以直接退出
41+
break
42+
if nums[i] + nums[j] + nums[length - 2] + nums[length - 1] < target:
43+
continue
44+
45+
L = j + 1
46+
R = length - 1
47+
while L < R:
48+
sum_ = nums[i] + nums[j] + nums[L] + nums[R]
49+
if sum_ < target:
50+
L += 1
51+
continue
52+
elif sum_ > target:
53+
R -= 1
54+
continue
55+
else:
56+
ans.append([nums[i], nums[j], nums[L], nums[R]])
57+
L += 1
58+
R -= 1
59+
while L < R and nums[L] == nums[L-1]:
60+
L += 1
61+
while L < R and nums[R] == nums[R+1]:
62+
R -= 1
63+
64+
return ans
65+
```

‎pic/leetcode_array/15_1.gif‎

48.2 KB
Loading

0 commit comments

Comments
 (0)