KK's blog

每天积累多一些

0%

Posted on Edited on Disqus:

LeetCode



You are given a 2D array of integers envelopes where envelopes[i] = [w<sub>i</sub>, h<sub>i</sub>] represents the width and the height of an envelope.

One envelope can fit into another if and only if both the width and height of one envelope are greater than the other envelope’s width and height.

Return the maximum number of envelopes you can Russian doll (i.e., put one inside the other).

Note: You cannot rotate an envelope.

Example 1:

Input: envelopes = [[5,4],[6,4],[6,7],[2,3]]
Output: 3
Explanation: The maximum number of envelopes you can Russian doll is 3 ([2,3] => [5,4] => [6,7]).


Example 2:

Input: envelopes = [[1,1],[1,1],[1,1]]
Output: 1


Constraints:

1 <= envelopes.length <= 5000 envelopes[i].length == 2
* 1 <= w<sub>i</sub>, h<sub>i</sub> <= 10<sup>4</sup>

题目大意：

信封套信封，能套上的条件是内信封的宽度和高度均小于外信封。求最多有多少个信封能套在一次

算法思路：

类似于LIS，先排序宽度，高度就变成LIS问题。

注意事项：

  1. 宽度和高度都是严格递增，所以排序envelopes的时候，先顺序排序宽度，再逆序排高度，逆序是防止同一宽度但高度不同的信封成为合法结果，如[3, 4], [3, 5], 高度LIS变成[4, 5]但不合法。还要注意Python语法：envelopes.sort(key=lambda x: (x[0], -x[1]))
  2. 用bisect_left因为，若高度相等，原地替换并不往后加。

Python代码：

1
2
3
4
5
6
7
8
9
10
def maxEnvelopes(self, envelopes: List[List[int]]) -> int:
	envelopes.sort(key=lambda x: (x[0], -x[1])) # remember format and reversed order
	sorted_height = []
	for i in range(len(envelopes)):
		index = bisect.bisect_left(sorted_height, envelopes[i][1]) # remember left
		if index < len(sorted_height):
			sorted_height[index] = envelopes[i][1]
		else:
			sorted_height.append(envelopes[i][1])
	return len(sorted_height)

Java代码：

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
public int maxEnvelopes(int[][] envelopes) {
	if(envelopes == null || envelopes.length == 0 || 
			envelopes[0] == null || envelopes[0].length != 2) // remember for 2d array
		return 0;
	Arrays.sort(envelopes, new Comparator<int[]>() {
		public int compare(int[] a, int[] b) {
			if(a[0] == b[0])
				return b[1] - a[1]; // remember the reverse order for [4,5], [4,6] case must strictly increasing for width and height
			else
				return a[0] - b[0];
		}
	});
	int len = 0;
	int[] lis = new int[envelopes.length];
	for(int[] e : envelopes) {
		int index = Arrays.binarySearch(lis, 0, len, e[1]);
		if(index < 0) {
			index = -index - 1;
			lis[index] = e[1];
		}
		else
			lis[index] = e[1];
		if(index == len)
			len++;
	}

	return len;
}

算法分析：

Insert时间复杂度为O(nlogn)，空间复杂度O(1)

Posted on Edited on Disqus:

LeetCode



Design and implement a data structure for a Least Frequently Used (LFU) cache.

Implement the LFUCache class:

LFUCache(int capacity) Initializes the object with the capacity of the data structure. int get(int key) Gets the value of the key if the key exists in the cache. Otherwise, returns -1.
void put(int key, int value) Update the value of the key if present, or inserts the key if not already present. When the cache reaches its capacity, it should invalidate and remove the least frequently used key before inserting a new item. For this problem, when there is a tie (i.e., two or more keys with the same frequency), the least recently used key would be invalidated.

To determine the least frequently used key, a use counter is maintained for each key in the cache. The key with the smallest use counter is the least frequently used key.

When a key is first inserted into the cache, its use counter is set to 1 (due to the put operation). The use counter for a key in the cache is incremented either a get or put operation is called on it.

The functions get and put must each run in O(1) average time complexity.

Example 1:

Input
[“LFUCache”, “put”, “put”, “get”, “put”, “get”, “get”, “put”, “get”, “get”, “get”]
[[2], [1, 1], [2, 2], [1], [3, 3], [2], [3], [4, 4], [1], [3], [4]]
Output
[null, null, null, 1, null, -1, 3, null, -1, 3, 4]

Explanation
// cnt(x) = the use counter for key x
// cache=[] will show the last used order for tiebreakers (leftmost element is  most recent)
LFUCache lfu = new LFUCache(2);
lfu.put(1, 1);   // cache=[1,_], cnt(1)=1
lfu.put(2, 2);   // cache=[2,1], cnt(2)=1, cnt(1)=1
lfu.get(1);      // return 1
                 // cache=[1,2], cnt(2)=1, cnt(1)=2
lfu.put(3, 3);   // 2 is the LFU key because cnt(2)=1 is the smallest, invalidate 2.
                 // cache=[3,1], cnt(3)=1, cnt(1)=2
lfu.get(2);      // return -1 (not found)
lfu.get(3);      // return 3
                 // cache=[3,1], cnt(3)=2, cnt(1)=2
lfu.put(4, 4);   // Both 1 and 3 have the same cnt, but 1 is LRU, invalidate 1.
                 // cache=[4,3], cnt(4)=1, cnt(3)=2
lfu.get(1);      // return -1 (not found)
lfu.get(3);      // return 3
                 // cache=[3,4], cnt(4)=1, cnt(3)=3
lfu.get(4);      // return 4
                 // cache=[3,4], cnt(4)=2, cnt(3)=3


Constraints: 0 <= capacity <= 10<sup>4</sup>
0 <= key <= 10<sup>5</sup> 0 <= value <= 10<sup>9</sup>
At most `2 105calls will be made togetandput`.

双Map+分区LL解题思路(推荐)：

类似于LRU，但本质上区别较大。一开始思路可参考算法II，它的缺点是move_up需要从该层的某个位置删除加入到上一个freq较大的下一层的末尾。为了避免此问题，考虑不用单一链表，而是对应不同freq的多个链表。所以引入freq_map来记录每个LL的起点。由于每个LL都是从旧到新（跟LRU一样），新的插入到末尾，删除的从头删除，所以需要是循环链表，最终是一个循环双向LL。ListNode的next和prev都指向自己

move_up解决了，另一个难点是get_lfu_node，这里引入min_freq来记录当前最小的freq。它的更新由三方面引起:新节点min_freq=1，get的move_up和旧节点move_up。后两者是一样的，都是move_up后查看min_freq所以的LL是否为空。

总结一下与LRU的区别：

  • set也是三种情况但要更新min_freq
  • ListNode多了freq，next prev指向自己形成循环LL，key，val含默认值
  • Cache中多了freq map和min_freq
  • 链表操作为move_up和get_lru_node，这点和算法II一样
  • 节点操作为remove_node, add_to_tail和LRU一样。add_to_tail是分层LL末尾不是总链表末尾

注意事项：

  1. 用了一小时debug min_freq的更新，move_up发生时候，检查min_freq所在的LL，若为空，增加1，而不是检查node_freq所在的LL。新节点令min_freq变成1
  2. 思路上：LRU是Map to Node in 全局双向LL，而LRU是Map to Node in 分区双向循环LL。存在多条LL，每个LL的起点终点存在freq map中。min_freq记录要删除的LFU节点对应的频率。
  3. 思路上：再LRU基础上增加freq域默认为1，key, val默认为0，prev和next指向自己，形成双向循环LL
  4. capacity可能为0，LRU那天capacity大于0
  5. 双向LL加入新节点有两个赋值语句，不要忘记node.prev, node.next = predecessor, successor

Python代码：

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
65
66
class LFUCache(TestCases):

    def __init__(self, capacity: int):
        self.key_to_node = collections.defaultdict(ListNode)
        self.freq_to_head = collections.defaultdict(ListNode)
        self.min_freq = 1
        self.capacity = capacity

    def get(self, key: int) -> int:
        if key in self.key_to_node:
            node = self.key_to_node[key]
            node_freq = node.freq
            self.move_up(node)
            # if self.freq_to_head[node_freq].next == self.freq_to_head[node_freq]:
              #  self.min_freq = node.freq
            if self.freq_to_head[self.min_freq].next == self.freq_to_head[self.min_freq]:
                self.min_freq += 1
            return node.val
        else:
            return -1

    def put(self, key: int, value: int) -> None:
        if key in self.key_to_node:
            node = self.key_to_node[key]
            node.val = value
            self.move_up(node)
            if self.freq_to_head[self.min_freq].next == self.freq_to_head[self.min_freq]:
                self.min_freq += 1
        elif self.capacity > 0:
            if len(self.key_to_node) == self.capacity:
                lru_node = self.get_lru_node()
                self.key_to_node.pop(lru_node.key)
                self.remove_node(lru_node)
            new_node = ListNode(key, value)
            self.add_to_tail(new_node)
            self.key_to_node[key] = new_node
            self.min_freq = 1

    def move_up(self, node):
        self.remove_node(node)
        node.freq += 1
        self.add_to_tail(node)

    def get_lru_node(self):
        head = self.freq_to_head[self.min_freq]
        return head.next

    def add_to_tail(self, node):
        head = self.freq_to_head[node.freq]
        predecessor, successor = head.prev, head
        predecessor.next, successor.prev = node, node
        node.prev, node.next = predecessor, successor

    def remove_node(self, node):
        predecessor, successor = node.prev, node.next
        predecessor.next, successor.prev = successor, predecessor
        node.prev, node.next = None, None

class ListNode:

    def __init__(self, key=0, val=0, freq=1):
        self.key = key
        self.val = val
        self.freq = freq
        self.prev = self # self-pointed
        self.next = self

算法分析：

Insert时间复杂度为O(1)，空间复杂度O(n)

类LRU算法II解题思路(不推荐)：

似乎Leetcode改变了要求，之前此法是可以通过的，但现在put要求O(1)了，所以TLE了。

注意事项：

  1. 再LRU基础上增加freq域默认为1，新节点插入doubly LL末尾，LL以freq从大到小，同一个频率从最旧到最新(LRU)。所以若满容量要删除节点从freq=1中往前找到该层的首节点
  2. capacity可能为0，LRU那天capacity大于0
  3. move_up是往前搜索, it = it.prev而不是用next。比较条件为it.freq < node.freq，加入到同一频率的末尾
  4. 双向LL加入新节点有两个赋值语句，不要忘记node.prev, node.next = predecessor, successor

Python代码：

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
65
class LFUCache(TestCases):

    def __init__(self, capacity: int):
        self.capacity = capacity
        self.key_to_node = collections.defaultdict(ListNode)
        # newly inserted to tail
        self.head, self.tail = ListNode(0, 0), ListNode(0, 0)
        self.head.next, self.tail.prev = self.tail, self.head

    def get(self, key: int) -> int:
        if key in self.key_to_node:
            self.move_up(self.key_to_node[key])
            return self.key_to_node[key].val
        else:
            return -1

    def put(self, key: int, value: int) -> None:
        if key in self.key_to_node:
            self.key_to_node[key].val = value
            self.move_up(self.key_to_node[key])
        elif self.capacity > 0: # remember
            if len(self.key_to_node) == self.capacity:
                node = self.get_lfu_node()
                self.key_to_node.pop(node.key)
                self.remove(node)
            new_node = ListNode(key, value)
            self.add_to_tail(new_node)
            self.key_to_node[key] = new_node

    def get_lfu_node(self):
        it = self.tail.prev
        min_freq = it.freq
        while it != self.head and it.freq == min_freq:
            it = it.prev # remember prev not next
        return it.next

    def move_up(self, node):
        node.freq += 1
        it = node.prev
        self.remove(node)
        while it != self.head and it.freq < node.freq: # remember <=
            it = it.prev # remember prev not next
        predecessor, successor = it, it.next
        predecessor.next, successor.prev = node, node
        node.prev, node.next = predecessor, successor

    def add_to_tail(self, node):
        predecessor, successor = self.tail.prev, self.tail
        predecessor.next, successor.prev = node, node
        node.prev, node.next = predecessor, successor # remember

    def remove(self, node):
        predecessor, successor = node.prev, node.next
        predecessor.next, successor.prev = successor, predecessor
        node.prev, node.next = None, None


class ListNode:

    def __init__(self, key, val, freq=1, prev=None, next=None):
        self.key = key
        self.val = val
        self.freq = freq
        self.prev = prev
        self.next = next

注意事项：

  1. 在LRU基础上，ListNode引入freq域， 当频率增加时候，找到新的频率对应的末节点插入。其它基本不变。插入最差是O(n). 要提高的话，需要加入map和minFreq来迅速定位下一个插入位置。第一个Map不变，但LL不再是一串，而是按频率大小的多串。

Java代码：

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
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
Map<Integer, ListNode> map;
ListNode head; // from most frequent to less
ListNode tail;
int capacity;
public L460LFUCache(int capacity) {
	this.capacity = capacity;
	head = new ListNode(-1, -1, Integer.MAX_VALUE);
	tail = new ListNode(-1, -1, Integer.MIN_VALUE);
	head.next = tail;
	tail.prev = head;
	map = new HashMap<>();
}

public int get(int key) {
	if(!map.containsKey(key))
		return -1;
	moveUp(key);
	return map.get(key).val;
}

public void put(int key, int value) {
	if(capacity == 0)
		return;
	
	if(map.containsKey(key)) {
		moveUp(key);
		map.get(key).val = value; // remember to update the value
	}
	else {
		if(map.size() == capacity) {
			map.remove(tail.prev.key);
			deleteNode(tail.prev);
		}
		// add new key
		ListNode newNode = new ListNode(key, value);
		addNode(newNode, tail);
		map.put(key, newNode);
		moveUp(key);
	}
}

void moveUp(int key) {
	ListNode curNode = map.get(key);
	curNode.addOne();
	ListNode iterNode = curNode;
	while(iterNode.freq <= curNode.freq)
		iterNode = iterNode.prev;
	if(iterNode != curNode) {
		deleteNode(curNode);
		addNode(curNode, iterNode.next);
	}
}

void addNode(ListNode curNode, ListNode nextNode) {
	ListNode prevNode = nextNode.prev;
	prevNode.next = curNode;
	curNode.prev = prevNode;
	curNode.next = nextNode;
	nextNode.prev = curNode;
}
// delete head node and updated node
void deleteNode(ListNode curNode) {
	ListNode nextNode = curNode.next;
	ListNode prevNode = curNode.prev;
	prevNode.next = nextNode;
	nextNode.prev = prevNode;
	curNode.next = null;
	curNode.prev = null;
}

public class ListNode {
	public int key;
	public int val;
	public int freq = 1;
	public ListNode next;
	public ListNode prev;

	public ListNode(int key, int val) {
		this.key = key;
		this.val = val;
	}
	
	public ListNode(int key, int val, int freq) {
		this.key = key;
		this.val = val;
		this.freq = freq;
	}
	
	public void addOne() {
		freq++;
	}
}

算法分析：

Insert时间复杂度为O(n)，空间复杂度O(k)

Posted on Edited on Disqus:

LeetCode



Given an array of points where points[i] = [x<sub>i</sub>, y<sub>i</sub>] represents a point on the X-Y plane and an integer k, return the k closest points to the origin (0, 0).

The distance between two points on the X-Y plane is the Euclidean distance (i.e., √(x<sub>1</sub> - x<sub>2</sub>)<sup>2</sup> + (y<sub>1</sub> - y<sub>2</sub>)<sup>2</sup>).

You may return the answer in any order. The answer is guaranteed to be unique (except for the order that it is in).

Example 1:



Input: points = [[1,3],[-2,2]], k = 1
Output: [[-2,2]]
Explanation:
The distance between (1, 3) and the origin is sqrt(10).
The distance between (-2, 2) and the origin is sqrt(8).
Since sqrt(8) < sqrt(10), (-2, 2) is closer to the origin.
We only want the closest k = 1 points from the origin, so the answer is just [[-2,2]].


Example 2:

Input: points = [[3,3],[5,-1],[-2,4]], k = 2
Output: [[3,3],[-2,4]]
Explanation: The answer [[-2,4],[3,3]] would also be accepted.


Constraints:

1 <= k <= points.length <= 10<sup>4</sup> -10<sup>4</sup> < x<sub>i</sub>, y<sub>i</sub> < 10<sup>4</sup>

算法思路：

最大堆

注意事项：

  1. 求最小距离用最大堆，距离的相反数入堆
  2. 与堆顶比较，跟模板一样仍然是大于号

Python代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
def kClosest(self, points: List[List[int]], k: int) -> List[List[int]]:
	if not points or not points[0]:
		return 0
	heap, res = [], []
	for i in range(len(points)):
		x, y = points[i][0], points[i][1] # x=-2, y=2
		if i < k: # i=1, k=1
			heapq.heappush(heap, (-(x * x + y * y), x, y)) # -10, 1, 3
		elif -(x * x + y * y) > heap[0][0]: # -8 > -10
			heapq.heapreplace(heap, (-(x * x + y * y), x, y)) # -8, -2, -2

	while heap:
		(dis, x, y) = heapq.heappop(heap) # -8, -2, -2
		res.append([x, y])
	return res

Java代码：

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
public int[][] kClosest(int[][] points, int K) {
	PriorityQueue<Point> maxHeap = new PriorityQueue<Point>(K,
			new Comparator<Point>() {
				@Override
				public int compare(Point o1, Point o2) {
					return distance(o2, o1); // descending
				}
			}
	);
	
	for(int i = 0; i < points.length; i++) {
		Point p = new Point(points[i][0], points[i][1]);
		if(maxHeap.size() < K)
			maxHeap.offer(p);
		else if(distance(p, maxHeap.peek()) < 0) {
			maxHeap.poll();
			maxHeap.offer(p);
		}
	}
	int[][] res = new int[K][2];
	int j = 0;
	while(!maxHeap.isEmpty()) {
		Point p = maxHeap.poll();
		res[j][0] = p.x;
		res[j][1] = p.y;
		j++;
	}
	return res;
}

int distance(Point o1, Point o2) {
	return (o1.x * o1.x + o1.y * o1.y) - (o2.x * o2.x + o2.y * o2.y);
}

class Point {
	 int x;
	 int y;
	 Point() { x = 0; y = 0; }
	 Point(int a, int b) { x = a; y = b; }
}

算法分析：

时间复杂度为O(nlogk)，空间复杂度O(k)

Posted on Edited on Disqus:

LeetCode

The n-queens puzzle is the problem of placing n queens on an n x n chessboard such that no two queens attack each other.



Given an integer n, return all distinct solutions to the n-queens puzzle. You may return the answer in any order.



Each solution contains a distinct board configuration of the n-queens’ placement, where ‘Q’ and ‘.’ both indicate a queen and an empty space, respectively.



 


Example 1:



Input: n = 4
Output: [[“.Q..”,”…Q”,”Q…”,”..Q.”],[“..Q.”,”Q…”,”…Q”,”.Q..”]]
Explanation: There exist two distinct solutions to the 4-queens puzzle as shown above


Example 2:



Input: n = 1
Output: [[“Q”]]


 


Constraints:




  • 1 <= n <= 9


题目大意：

八皇后问题，求所有解

Global dict算法思路(推荐)：

DFS填位法模板

注意事项：

  1. 用3个set，col_set, 对角线，反对角线set来提高效率。
  2. path用append的方法加入，这样终止条件用n来比较，不能用len(path)
  3. 打印函数中，one_result在每轮后reset；字符串不能改其中一个，只能用子串+Q+子串： (‘.’ path[i]) + ‘Q’ + (‘.’ (n - path[i] - 1))

Python代码：

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
def solveNQueens(self, n: int) -> List[List[str]]:
	res, path = [], []
	self.dfs(n, 0, path, res, set(), set(), set())
	result = self.convert(res)
	return result

def dfs(self, n, start, path, res, col_set, diag_set, anti_diag_set):
	if start == n: # remember not len(path)
		res.append(list(path))
		return
	for i in range(n): # 4
		if not self.is_valid(start, i, col_set, diag_set, anti_diag_set):
			continue
		path.append(i)  # [0, 2]
		col_set.add(i)
		diag_set.add(start - i)
		anti_diag_set.add(start + i)
		self.dfs(n, start + 1, path, res, col_set, diag_set, anti_diag_set)
		anti_diag_set.remove(start + i)
		diag_set.remove(start - i)
		col_set.remove(i)
		path.pop()

def is_valid(self, i, val, col_set, diag_set, anti_diag_set):
	if val in col_set or i - val in diag_set or i + val in anti_diag_set:
		return False
	return True

算法分析：

时间复杂度为O(n!)，空间复杂度O(n^2)

常数空间算法II解题思路(推荐)：

较直观的方法，但复杂度稍差

Python代码：

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
def solveNQueens2(self, n: int) -> List[List[str]]:
	res, path = [], []
	self.dfs2(n, 0, path, res)
	result = self.convert(res)
	return result

def dfs2(self, n, start, path, res):
	if start == n: # remember not len(path)
		res.append(list(path))
		return
	for i in range(n): # 4
		path.append(i) # [0, 2]
		if self.is_valid2(path):
			self.dfs2(n, start + 1, path, res)
		path.pop()

def is_valid2(self, path):
	if len(path) != len(set(path)):
		return False
	for i in range(len(path)):
		for j in range(i + 1, len(path)):
			#if i == j:
			 #   continue
			if abs(i - j) == abs(path[i] - path[j]):
				return False
	return True

def convert(self, res):
	result, one_result = [], []
	for k in range(len(res)):
		one_result = [] # remember
		path = res[k]
		n = len(path)
		for i in range(n):
			s = ('.' * path[i]) + 'Q' + ('.' * (n - path[i] - 1))  # remember not s[path[i]] = 'Q'
			one_result.append(s)
		result.append(one_result)
	return result

Java代码：

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
public List<List<String>> solveNQueens2(int n) {
	List<List<String>> res = new ArrayList<>();
	int[] col = new int[n];
	solveR(n, col, 0, res);
	return res;
}

// 5/2/2020
void solveR(int n, int[] col, int st, List<List<String>> res) {
	if(st == n) {
		print(col, res);
		return;
	}
	
	for(int i = 0; i < n; i++) {
		col[st] = i;
		if(isValid(col, st))
			solveR(n, col, st + 1, res);
	}
}

boolean isValid(int[] col, int k) {
	for(int i = 0; i < k; i++) {
		if(col[i] == col[k])
			return false;
	}

	for(int i = 0; i < k; i++) {
		if(Math.abs(k - i) == Math.abs(col[k] - col[i])) //use abs
			return false;
	}
	return true;
}

算法分析：

时间复杂度为O(n!)，空间复杂度O(n^2)

Posted on Edited on Disqus:

LeetCode



Given an integer array nums, return all the triplets [nums[i], nums[j], nums[k]] such that i != j, i != k, and j != k, and nums[i] + nums[j] + nums[k] == 0.

Notice that the solution set must not contain duplicate triplets.

Example 1:

Input: nums = [-1,0,1,2,-1,-4]
Output: [[-1,-1,2],[-1,0,1]]


Example 2:

Input: nums = []
Output: []


Example 3:

Input: nums = [0]
Output: []


Constraints:

0 <= nums.length <= 3000 -10<sup>5</sup> <= nums[i] <= 10<sup>5</sup>

算法思路：

N/A

注意事项：

  1. 先排序
  2. 结果要去重，用i, j, k指针比较前一个元素，若相等指针移动跳过，k是比较后一个元素
  3. 注意指针移动，等于target两指针都要移动，若与前一元素相等，相应指针移一位，要避免死循环

Python代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
def threeSum(self, nums: List[int]) -> List[List[int]]:
	nums.sort()
	res = []
	for i in range(len(nums)):
		if i > 0 and nums[i] == nums[i - 1]:
			continue
		sub_res = self.two_sum(nums, i + 1, -nums[i])
		for li in sub_res:
			res.append([nums[i]] + li)
	return res

def two_sum(self, nums, start, target):
	j, k, res = start, len(nums) - 1, []
	while j < k:
		if (j > start and nums[j] == nums[j - 1]) or nums[j] + nums[k] < target:
			j += 1
		elif (k < len(nums) - 1 and nums[k] == nums[k + 1]) or nums[j] + nums[k] > target:
			k -= 1
		elif nums[j] + nums[k] == target:
			res.append([nums[j], nums[k]])
			j += 1
			k -= 1
	return res

Java代码：

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
public List<List<Integer>> threeSum2(int[] nums) {
	List<List<Integer>> re = new ArrayList<>();
	if(nums == null || nums.length == 0)
		return re;
	Arrays.sort(nums);
	for(int i = 0; i < nums.length - 2; i++) {
		if(i > 0 && nums[i] == nums[i-1])
			continue;
		twoPointers(nums, i + 1, nums.length - 1, -nums[i], re);
	}
	return re;
}

void twoPointers(int[] nums, int left, int right, int target, List<List<Integer>> re) {
	int leftOri = left, rightOri = right;
	while(left < right) {
		if(left > leftOri && nums[left] == nums[left-1]) {
			left++;
			continue;
		}
		if(right < rightOri && nums[right] == nums[right + 1]) {
			right--;
			continue;
		}
		
		if(nums[left] + nums[right] == target) 
			re.add(Arrays.asList(-target, nums[left++], nums[right--]));
		else if(nums[left] + nums[right] < target)
			left++;
		else 
			right--;
	}
}

算法分析：

时间复杂度为O(n^2)，空间复杂度O(1)

Free mock interview