KK's blog

每天积累多一些

0%

LeetCode 015 3Sum

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