LeetCode 15. 三数之和
题目描述
🔥 15. 三数之和
思路分析
排序+双指针
参考代码
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
func threeSum(nums []int) [][]int {
sort.Ints(nums)
var res [][]int
for i := 0; i < len(nums)-2; i++ {
// 跳过重复元素
if i > 0 && nums[i] == nums[i-1] {
continue
}
left, right := i+1, len(nums)-1
for left < right {
sum := nums[i] + nums[left] + nums[right]
if sum == 0 {
res = append(res, []int{nums[i], nums[left], nums[right]})
// 跳过重复元素
for left < right && nums[left] == nums[left+1] {
left++
}
for left < right && nums[right] == nums[right-1] {
right--
}
left++
right--
} else if sum < 0 {
left++
} else {
right--
}
}
}
return res
}
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
func threeSum(nums []int) [][]int {
res := make([][]int, 0)
if len(nums) <= 2 {
return res
}
sort.Ints(nums)
for i := 0; i < len(nums)-2; i++ {
if i > 0 && nums[i] == nums[i-1] {
continue
}
target := -nums[i]
left, right := i+1, len(nums)-1
for left < right {
twoSum := nums[left] + nums[right]
if twoSum == target {
res = append(res, []int{-target, nums[left], nums[right]})
left++
right--
for left < right && nums[left] == nums[left-1] {
left++
}
for left < right && nums[right] == nums[right+1] {
right--
}
} else if twoSum > target {
right--
} else {
left++
}
}
}
return res
}
- 时间复杂度：O (n^2)，其中 n 是数组的长度。排序的时间复杂度为 O (n log n)，双指针查找的时间复杂度为 O (n)。
- 空间复杂度：O (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
class Solution {
public List<List<Integer>> threeSum(int[] nums) {
List<List<Integer>> res = new ArrayList<>();
if (nums == null || nums.length <= 2) {
return res;
}
Arrays.sort(nums);
int n = nums.length;
for (int i = 0; i < n - 2; i++) {
if (i > 0 && nums[i] == nums[i - 1]) {
continue;
}
int target = -nums[i];
int left = i + 1, right = n - 1;
while (left < right) {
int sum = nums[left] + nums[right];
if (sum == target) {
res.add(new ArrayList<>(Arrays.asList(-target, nums[left], nums[right])));
left++;
right--;
while (left < right && nums[left] == nums[left - 1]) {
left++;
}
while (left < right && nums[right] == nums[right + 1]) {
right--;
}
} else if (sum > target) {
right--;
} else {
left++;
}
}
}
return res;
}
}
本博客所有文章除特别声明外，均采用
CC BY-NC-SA 4.0
许可协议，转载请注明出处！