- 3Sum 难度 中等
https://leetcode-cn.com/problems/3sum/
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
-105 <= nums[i] <= 105
相关企业
- 字节跳动|27
- 亚马逊 Amazon|21
- 苹果 Apple|18
- Facebook|18
- 谷歌 Google|9
相关标签
- Array
- Two Pointers
- Sorting
相似题目
- Two Sum简单
- 3Sum Closest中等
- 4Sum中等
- 3Sum Smaller中等
方法1: 暴力枚举三个数复杂度为O(N^3) C^3_n
方法2:
先考虑2Sum的做法，假设升序数列a，对于一组解ai,aj, 另一组解ak,al 必然满足 i<k j>l 或 i>k j<l, 因此我们可以用两个指针，初始时指向数列两端 指向数之和大于目标值时，右指针向左移使得总和减小，反之左指针向右移 由此可以用 O(N)的复杂度解决2Sum问题，3Sum则枚举第一个数 O(N^2)。
使用有序数列的好处是，在枚举和移动指针时值相等的数可以跳过，省去去重部分
forloop each element then call find_two_sum()
class Solution:
def threeSum(self, nums: List[int]) -> List[List[int]]:
if (not nums) or len(nums) < 3:
return []
nums = sorted(nums)
result = []
for target in nums:
self.find_two_sum(nums, 0 - target, result)
return result
def find_two_sum(self, nums, target: int, result: List[List[int]]) -> List[List[int]]:
if not nums:
return [[]]
# remove the target which is already an element
nums_temp = nums.copy()
nums_temp.remove(0-target)
left, right = 0, len(nums_temp) - 1
while (left < right):
if nums_temp[left] + nums_temp[right] < target:
left += 1
elif nums_temp[left] + nums_temp[right] > target:
right -= 1
else:
triplet = [nums_temp[left], nums_temp[right], 0 - target]
triplet = sorted(triplet) # avoid repeat results
if triplet not in result:
result.append(triplet)
left += 1
right -= 1
return result
- repeat "target" can skip (because it is sorted)
- don't use whole "nums" when call find_two_sum(), then don't need to remove "target" element.
- Only use partial array. Give left/right to find_two_sum(). A+B=-C. Because it it sorted so twosum of -C must be right part of C.
class Solution:
def threeSum(self, nums: List[int]) -> List[List[int]]:
if (not nums) or len(nums) < 3:
return []
nums = sorted(nums)
result = []
for i in range(0, len(nums) - 1 - 1):
if i > 0 and nums[i] == nums[i - 1]:
continue # (because it is sorted)
self.find_two_sum(nums, 0 - nums[i], i + 1, len(nums) - 1, result) # use 0-nums[i] as target
return result
def find_two_sum(self, nums, target: int, left: int, right: int, result: List[List[int]]) -> List[List[int]]:
if not nums:
return [[]]
while (left < right):
if nums[left] + nums[right] < target:
left += 1
elif nums[left] + nums[right] > target:
right -= 1
else:
triplet = [nums[left], nums[right], 0 - target]
triplet = sorted(triplet)
if triplet not in result:
result.append(triplet)
left += 1
right -= 1
return result
- triplet [-target, nums[left], nums[right]] then no need to sort
class Solution:
def threeSum(self, nums: List[int]) -> List[List[int]]:
if (not nums) or len(nums) < 3:
return []
nums = sorted(nums)
results = []
length = len(nums)
for i in range(0, length - 2):
if i > 0 and nums[i] == nums[i - 1]:
continue
self.find_two_sum(nums, -nums[i], i + 1, length - 1, results)
return results
def find_two_sum(self, nums, target, left, right, results):
while left < right:
if nums[left] + nums[right] == target:
results.append([-target, nums[left], nums[right]]) #order by hand
right -= 1
left += 1
# faster by skipping same result
while left < right and nums[left] == nums[left - 1]:
left += 1
while left < right and nums[right] == nums[right + 1]:
right -= 1
elif nums[left] + nums[right] > target:
right -= 1
else:
left += 1class Solution {
public List<List<Integer>> threeSum(int[] nums) {
List<List<Integer>> result = new ArrayList<List<Integer>>();
if (nums == null || nums.length < 3){
return result;
}
Arrays.sort(nums);
for (int i = 0; i < nums.length; i++){
if (i > 0 && nums[i] == nums[i-1]){
continue;
}
this.findTwoSum(nums, 0-nums[i], i+1, nums.length-1, result);
}
return result;
}
public void findTwoSum(int[] nums, int target, int left, int right, List<List<Integer>> result){
while (left < right){
if (nums[left] + nums[right] == target){
List<Integer> triplet = new ArrayList<Integer>();
triplet.add(0-target); // add by order, no need to sort and check existing
triplet.add(nums[left]);
triplet.add(nums[right]);
result.add(triplet);
left += 1;
right -= 1;
while (left < right && nums[left] == nums[left-1]){
left += 1;
}
while (left < right && nums[right] == nums[right+1]){
right -= 1;
}
}else if (nums[left] + nums[right] < target){
left += 1;
}else {
right -= 1;
}
}
}
}func threeSum(nums []int) [][]int {
if nums == nil || len(nums) <= 2 {
return [][]int{}
}
sort.Ints(nums)
results := [][]int{}
for i := 0; i < len(nums)-2; i++ {
if i > 0 && nums[i] == nums[i-1] { continue }
twoSumResults := findTwoSum(nums, -nums[i], i+1, len(nums)-1)
for _, v := range(twoSumResults){
found := ElemExistInArray(results, v)
if !found {
results = append(results, v)
}
}
}
return results
}
func findTwoSum(nums []int, target int, left int, right int) ([][]int){
result := [][]int{}
for left < right {
twosum := nums[left] + nums[right]
if twosum == target {
result = append(result, []int{-target, nums[left], nums[right]}) // no need check existing because it must be different as different target
left += 1
right -= 1
for left < right && nums[left] == nums[left-1] {
left ++
}
for left < right && nums[right] == nums[right+1]{
right --
}
}else if twosum < target {
left ++
}else if twosum > target {
right --
}
}
return result
}
func ElemExistInArray(nums [][]int, want []int) bool{
for _, v := range nums{
if TwoSlicesEqual(v, want) {
return true
}
}
return false
}
func TwoSlicesEqual(a []int, b []int) bool {
if len(a) != len(b) {
return false
}
for i, v := range a {
if v != b[i] {
return false
}
}
return true
}