15 - 3Sum
Written on October 21, 2015
Tweet
Given an array S of n integers, are there elements a, b, c in S such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero.
public class Solution {
public List<List<Integer>> threeSum(int[] nums) {
List<List<Integer>> result = new ArrayList<List<Integer>>();
if (nums == null || nums.length == 0) return result;
Arrays.sort(nums);
for (int i = 0; i + 2 < nums.length; i++) {
if (i > 0 && nums[i] == nums[i - 1]) continue;
int lo = i + 1, hi = nums.length - 1;
while (lo < hi) {
if (lo > i + 1 && nums[lo] == nums[lo - 1]) {
lo++;
continue;
}
if (hi < nums.length - 1 && nums[hi] == nums[hi + 1]) {
hi--;
continue;
}
int sum = nums[i] + nums[lo] + nums[hi];
if (sum == 0) {
List<Integer> list = new ArrayList<Integer>(Arrays.asList(nums[i], nums[lo], nums[hi]));
result.add(list);
lo++;
hi--;
} else if (sum < 0) {
lo++;
} else {
hi--;
}
}
}
return result;
}
}
class Solution(object):
def threeSum(self, nums):
"""
:type nums: List[int]
:rtype: List[List[int]]
"""
if not nums:
return []
ret = []
nums.sort()
for i, num in enumerate(nums[:-2]):
if i > 0 and nums[i] == nums[i - 1]:
continue
lo, hi = i + 1, len(nums) - 1;
while lo < hi:
if lo > i + 1 and nums[lo] == nums[lo - 1]:
lo += 1
continue
if hi < len(nums) - 1 and nums[hi] == nums[hi + 1]:
hi -= 1
continue
if nums[lo] + nums[hi] + num == 0:
ret.append([num, nums[lo], nums[hi]])
lo += 1
hi -= 1
elif nums[lo] + nums[hi] + num > 0:
hi -= 1
else:
lo += 1
return ret
