Note:
- Elements in a triplet (a,b,c) must be in non-descending order. (ie, a ≤ b ≤ c)
- 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)
public class Solution { public List<List<Integer>> threeSum(int[] num) { List<List<Integer>> list = new LinkedList<>(); int n = num.length; if (n < 3) return list; Arrays.sort(num); int left, right, sum; for (int i = 0; i <= n-3; i++) { left = i+1; right = n-1; if (i==0 || num[i]>num[i-1]) { while (left < right) { sum = num[i]+num[left]+num[right]; if (sum < 0) left++; else if (sum > 0) right--; else { List<Integer> ret = new LinkedList<>(); ret.add(num[i]); ret.add(num[left]); ret.add(num[right]); list.add(ret); left++; right--; // Avoid duplicate solutions while (left<right && num[right]==num[right+1]) right--; while (left<right && num[left]==num[left-1]) left++; } } } } return list; } }
No comments:
Post a Comment