15 3Sum
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.
Note: The solution set must not contain duplicate triplets.
For example, given array S = [-1, 0, 1, 2, -1, -4],
A solution set is:
[
[-1, 0, 1],
[-1, -1, 2]
]
分析&代码
和Two sum pointer版差不多，需要注意的是，可能有重复数字，所以
- 如果最外层循环中发现，现在的和前一个是一样就continue
- 如果一旦找到一组答案，检查walker和runner的位置，如果它们下一位和它们相同，就移动它们
原博客的内容：
如果不用hashmap解决2sum，而是把2sum看成nSum中的一部分，那么就需要用two pointers来解决问题。
2sum伪代码：
先对给定的数组进行排序
walker指第一个元素，runner指最后一个元素
3.当walker小于runner：
1）如果walker和runner的和等于target，那么：
（1）如果只需要一对解，记录答案，break
（2）如果需要所有解，那么walker++, runner--.
同时，为了节省时间，如果walker<runner && nums[walker]==nums[walker-1]时，walker++,并且如果walker<runner&&nums[runner]==nums[runner=1]时，runner--
2） else如果和小于target，walker++
3） else runner++
4.返回结果
算法时间复杂度
- 2sum的时间复杂度
排序的复杂度是O(NlogN), 然后再就是最多从头到尾走一遍，所以是O(N), 所以复杂度是O(N+NlogN)，所以是O(N)
- 3sum时间复杂度是
排序的时间复杂度O(NLogN), 在对于每一个数组做2sum，但是这个时候的2sum不需要排序，所以这个2sum是O(N)，所以这部分的时间复杂度是O(N^2）
所以总时间复杂度是O(N^2+NLogN)= O(N^2)
public List<List<Integer>> threeSum(int[] nums) {
List<List<Integer>> res = new ArrayList<>();
if(nums.length == 0) {
return res;
}
Arrays.sort(nums);
int len = nums.length;
for(int i = 0; i < len - 2; i++) {
if(i == 0 || (i > 0 && nums[i-1] != nums[i])) {
int walker = i + 1;
int runner = len - 1;
while(walker < runner) {
if(nums[walker] + nums[runner] == -nums[i]) {
res.add(new ArrayList<Integer>(Arrays.asList(nums[i], nums[walker], nums[runner])));
while(walker < runner && nums[walker] == nums[walker + 1]) {
walker++;
}
while(walker < runner && nums[runner] == nums[runner - 1]) {
runner--;
}
walker++;
runner--;
} else if(nums[walker] + nums[runner] < -nums[i]) {
walker++;
} else {
runner--;
}
}
}
}
return res;
}