15. 三数之和

原题链接：

15. 三数之和

https://leetcode.cn/problems/3sum/description/

完成情况：

解题思路：

排序 + 双指针
本题的难点在于如何去除重复解。

算法流程：
特判，对于数组长度 nnn，如果数组为 nullnullnull 或者数组长度小于 333，返回 [][][]。
对数组进行排序。
遍历排序后数组：
若 nums[i]>0nums[i]>0nums[i]>0：因为已经排序好，所以后面不可能有三个数加和等于 000，直接返回结果。
对于重复元素：跳过，避免出现重复解
令左指针 L=i+1L=i+1L=i+1，右指针 R=n−1R=n-1R=n−1，当 L 当 nums[i]+nums[L]+nums[R]==0nums[i]+nums[L]+nums[R]==0nums[i]+nums[L]+nums[R]==0，执行循环，判断左界和右界是否和下一位置重复，去除重复解。并同时将 L,RL,RL,R 移到下一位置，寻找新的解
若和大于 000，说明 nums[R]nums[R]nums[R] 太大，RRR 左移
若和小于 000，说明 nums[L]nums[L]nums[L] 太小，LLL 右移
复杂度分析
时间复杂度：O(n2)O\left(n^{2}\right)O(n
2
)，数组排序 O(Nlog⁡N)O(N \log N)O(NlogN)，遍历数组 O(n)O\left(n\right)O(n)，双指针遍历 O(n)O\left(n\right)O(n)，总体 O(Nlog⁡N)+O(n)∗O(n)O(N \log N)+O\left(n\right)*O\left(n\right)O(NlogN)+O(n)∗O(n)，O(n2)O\left(n^{2}\right)O(n
2
)
空间复杂度：O(1)O(1)O(1)
Python

参考代码：

__15三数之和__官方题解

package 日常Java程序测试.代码随想录.哈希表;

import java.util.*;

public class __15三数之和__官方题解 {
	/**
	 *  3 <= nums.length <= 3000
	 *  //那这里就不行暴力三个for了
	 * -10^5 <= nums[i] <= 10^5
	 *
	 *
	 * 三个数的话，可以仿造之前四个数的搞一下
	 * 然后这道题也没有时间要求，基本就是自己随便玩
	 * 然后结果集的话，需要构建一个链表
	 *
	 * @param nums
	 * @return
	 */
	public List<List<Integer>> threeSum(int[] nums) {
		Map<Integer,Integer> map = new HashMap<Integer,Integer>();
		List<List<Integer>> res = new ArrayList<List<Integer>>();
		//这道题是一个数组里面找三个值
		/*
		先将原来的元素排好序的话，可以减少大量的重复操作
		 */
		int n = nums.length;
		Arrays.sort(nums);
		//枚举所有a
		for (int first = 0;first<n;++first){
			//需要和上次枚举的数不相同
			if (first > 0 && nums[first] == nums[first-1]){
				continue;
			}
			//c对应的指针初始化指向数组的最右端
			int third = n - 1;
			int target = -nums[first];
			//枚举b
			for (int second = first+1;second<n;++second){
				//需要和上次枚举的数不相同
				if (second > first + 1 && nums[second] == nums[second - 1]){
					continue;
				}
				//需要保证b的指针在c的指针的左侧
				while (second<third && nums[second] + nums[third] > target){
					--third;
				}
				//如果指针重合，随着b后续的增加
				//就不会有满足a+b+c=0，并且b
				if (second == third){
					break;
				}
				if (nums[second] + nums[third] == target){
					List<Integer> list = new ArrayList<Integer>();
					list.add(nums[first]);
					list.add(nums[second]);
					list.add(nums[third]);
					res.add(list);
				}
			}
		}
		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
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

__15三数之和__优化

package 日常Java程序测试.代码随想录.哈希表;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class __15三数之和__优化 {
	public List<List<Integer>> threeSum(int[] nums) {
		Arrays.sort(nums);
		List<List<Integer>> ans = new ArrayList<>();
		int n = nums.length;
		for (int i = 0; i < n - 2; ++i) {
			int x = nums[i];
			if (i > 0 && x == nums[i - 1]) {
				continue; // 跳过重复数字
			}
			if (x + nums[i + 1] + nums[i + 2] > 0) {
				break; // 优化一
			}
			if (x + nums[n - 2] + nums[n - 1] < 0) {
				continue; // 优化二
			}
			int j = i + 1, k = n - 1;
			while (j < k) {
				int s = x + nums[j] + nums[k];
				if (s > 0) {
					--k;
				}
				else if (s < 0) {
					++j;
				}
				else {
					//List.of（） 生成不可变数组（字符串也行）
					// 是在jdk1.8以后才出现的，在jdk1.9版本及以后才能运行。 所以用1.8的盆友是不会代码补全的
					//ans.add(List.of(x, nums[j], nums[k]));
					for (++j; j < k && nums[j] == nums[j - 1]; ++j){}; // 跳过重复数字
					for (--k; k > j && nums[k] == nums[k + 1]; --k){}; // 跳过重复数字
				}
			}
		}
		return ans;
	}
}

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

错误经验吸取