问题描述
https://leetcode.com/problems/3sum/
解决思路
- sort the nums
- get a number in nums, let’s say a, and expect the sum of two other numbersis -a
- set left pointer and right pointer in the rest of the nums,
- if the result of left plus right is smaller than -a, then move the left pointer to right
- if the result of right plus left is bigger than -a, then move the right pointer to left
- we also need to pay attention to avoid repeat 这道题好多重复情况啊！！！！太恐怖了！！！
代码
class Solution {
public static List<List<Integer>> threeSum(int[] nums){
//0. sort the nums
//1. get a number in nums, let's say a, and expect the sum of two other numbers
//is -a
//2. set left pointer and right pointer in the rest of the nums,
//3. if the result of left plus right is smaller than -a, then move the left pointer to right
//4. if the result of right plus left is bigger than -a, then move the right pointer to left
//5. we also need to pay attention to avoid repeat
ArrayList<List<Integer>> res = new ArrayList<List<Integer>>();
//corner case
if(nums == null || nums.length < 2) return res;
int n = nums.length;
int i = 0;
Arrays.sort(nums);
while(i < n - 2) {
int base = nums[i];
int left = i + 1;
int right = n - 1;
while(left < right) {
int sum = base + nums[left] + nums[right];
//find the solution
if(sum == 0) {
LinkedList<Integer> list = new LinkedList<Integer>();
list.add(base);
list.add(nums[left]);
list.add(nums[right]);
res.add(list);
left = moveRight(nums, left + 1);
right = moveLeft(nums, right - 1);
}else if(sum > 0) {
right = moveLeft(nums, right - 1);
}else {
left = moveRight(nums, left + 1);
}
}
i = moveRight(nums, i + 1);
}
return res;
}
private static int moveLeft(int[] nums, int right) {
//if the next is the same as current, right continue to move
while(right == nums.length - 1 || (right >= 0 && nums[right] == nums[right + 1])) {
right--;
}
return right;
}
private static int moveRight(int[] nums, int left) {
while(left == 0 || (left < nums.length && nums[left] == nums[left - 1])) {
left++;
}
return left;
}
}
复杂度分析
- 时间复杂度：O(N^2)
- 空间复杂度：O(N^2)
