Time = O(n^2)
双指针。注意这种做法要先把数组排序。
去重：不论是 base指针，还是 left指针，都要找到下一个不相等的数。
https://leetcode.com/problems/3sum/discuss/7399/Easiest-Java-Solution
class Solution {
public List<List<Integer>> threeSum(int[] nums) {
List<List<Integer>> res = new ArrayList<>();
if (nums == null || nums.length < 3) {
return res;
}
Arrays.sort(nums);// important!!
for (int i = 0; i < nums.length - 2; i++) {
if (i != 0 && nums[i - 1] == nums[i]) {
continue;
}
int left = i + 1;
int right = nums.length - 1;
while (left < right) {
int curSum = nums[i] + nums[left] + nums[right];
if (curSum == 0) {
List<Integer> cur = Arrays.asList(nums[i], nums[left], nums[right]);
res.add(cur);
left ++;
right --;
while (left < right && nums[left] == nums[left - 1]) {
left ++;
}
while (left < right && nums[right] == nums[right + 1]) {
right --;
}
} else if (curSum < 0) {
left ++;
} else {
right --;
}
}
}
return res;
}
}
Python:
class Solution:
def threeSum(self, nums):
"""
:type nums: List[int]
:rtype: List[List[int]]
"""
res = []
if not nums or len(nums) < 3:
return res
nums.sort()
for i in range(len(nums) - 2):
if i != 0 and nums[i - 1] == nums[i]:
continue
l, r = i + 1, len(nums) - 1
while l < r:
if nums[i] + nums[l] + nums[r] == 0:
res.append([nums[i], nums[l], nums[r]])
l, r = self.move_left(i, l, r, nums)
l, r = self.move_right(l, r, nums)
elif nums[i] + nums[l] + nums[r] < 0:
l, r = self.move_left(i, l, r, nums)
else:
l, r = self.move_right(l, r, nums)
return res
def move_left(self, i, l, r, nums):
l += 1
while l < r and l != i + 1 and nums[l] == nums[l - 1]:
l += 1
return l, r
def move_right(self, l, r, nums):
r -= 1
while l < r and r != len(nums) - 1 and nums[r] == nums[r + 1]:
r -= 1
return l, r
class Solution:
def threeSum(self, nums):
"""
:type nums: List[int]
:rtype: List[List[int]]
"""
res = []
if not nums or len(nums) < 3:
return res
nums.sort()
for i in range(len(nums) - 2):
if i != 0 and nums[i - 1] == nums[i]:
continue
l, r = i + 1, len(nums) - 1
while l < r:
if nums[i] + nums[l] + nums[r] == 0:
res.append([nums[i], nums[l], nums[r]])
l += 1
while l < r and l != i + 1 and nums[l] == nums[l - 1]:
l += 1
r -= 1
elif nums[i] + nums[l] + nums[r] < 0:
l += 1
else:
r -= 1
return res