给你一个包含 n 个整数的数组 nums,判断 nums 中是否存在三个元素 a,b,c ,使得 a + b + c = 0 ?请你找出所有满足条件且不重复的三元组。
注意:答案中不可以包含重复的三元组。
示例:
给定数组 nums = [-1, 0, 1, 2, -1, -4],
满足要求的三元组集合为: [ [-1, 0, 1], [-1, -1, 2] ]
题解 双指针法 若要找出所有满足条件的解,需三个变量 a
, b
, c
的所有情况且不能重复,若直接遍历时间复杂度为 O(N³)
,本题的关键在于如何降低时间复杂度和去除重复解。
可采用双指针法来实现遍历的不重不漏,首先将数组进行排序,再使L
指向 i+1
,R
指向末尾元素,两指针向中间移动直至相遇为止。在遍历过程中
若 nums[i]
与 nums[i-1]
、nums[L]
与 nums[L+1]
、nums[R]
与 nums[R-1]
相等即说明遇到了重复元素,跳过即可;
若 nums[i] + nums[L] + nums[R] == target
,即为一组解,L
和 R
同时移动;
若 nums[i] + nums[L] + nums[R] > target
,R
应向左移动以减小三数之和;
若 nums[i] + nums[L] + nums[R] < target
,L
应向右移动以增大三数之和。
时间复杂度
时间复杂度:O(N²)
,数组排序 O(NlogN)
,遍历数组 O(N)
,双指针遍历 O(N)
,总体为 O(NlogN) + O(N) * O(N)
,O(N²)
空间复杂度:O(1)
参考题解:LeetCode
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 import java.util.List;import java.util.ArrayList;import java.util.Arrays;public class Solution { public List<List<Integer>> threeSum (int [] nums) { int listLen = nums.length; List<List<Integer>> results = new ArrayList <>(); if (listLen < 3 ) return results; Arrays.sort(nums); int L, R; for (int i = 0 ; i < listLen; i++) { if (nums[i] > 0 ) return results; if (i > 0 && nums[i] == nums[i - 1 ]) continue ; L = i + 1 ; R = listLen - 1 ; while (L < R) { if (nums[i] + nums[L] + nums[R] == 0 ) { results.add(new ArrayList <>(Arrays.asList(nums[i], nums[L], nums[R]))); while (L < R && nums[L] == nums[L + 1 ]) L++; while (L < R && nums[R] == nums[R - 1 ]) R--; L++; R--; } else if (nums[i] + nums[L] + nums[R] > 0 ) { R--; } else { L++; } } } return results; } }
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 class Solution : def threeSum (self, nums: list ) -> list : list_len = len (nums) results = [] if not nums or list_len < 3 : return results nums.sort() for i in range (list_len): if nums[i] > 0 : return results if (i > 0 and nums[i] == nums[i - 1 ]): continue L = i + 1 R = list_len - 1 while L < R: if nums[i] + nums[L] + nums[R] == 0 : results.append([nums[i], nums[L], nums[R]]) while L < R and nums[L] == nums[L + 1 ]: L += 1 while L < R and nums[R] == nums[R - 1 ]: R -= 1 L += 1 R -= 1 elif nums[i] + nums[L] + nums[R] > 0 : R -= 1 else : L += 1 return results
Go 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 package mainimport ( "sort" ) func threeSum (nums []int ) [][]int { arrLen := len (nums) var results [][]int if nums == nil || arrLen < 3 { return results } sort.Ints(nums) for i := 0 ; i < arrLen; i++ { if nums[i] > 0 { return results } if i > 0 && nums[i] == nums[i-1 ] { continue } L, R := i+1 , arrLen-1 for L < R { if nums[i]+nums[L]+nums[R] == 0 { results = append (results, []int {nums[i], nums[L], nums[R]}) for L < R && nums[L] == nums[L+1 ] { L++ } for L < R && nums[R] == nums[R-1 ] { R-- } L++ R-- } else if nums[i]+nums[L]+nums[R] > 0 { R-- } else { L++ } } } return results }