Given an array nums of n integers, are there elements a, b, c in nums 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.
Example:
Given array nums = [-1, 0, 1, 2, -1, -4], A solution set is: [ [-1, 0, 1], [-1, -1, 2] ]
Idea: Simplify this problem from O(n^3) to n square by using two pointers
iterate i and j = i+1 and k = n-1 (j and k are two pointers we would use)
class Solution { public List<List<Integer>> threeSum(int[] nums) { Arrays.sort(nums); List<List<Integer>> res = new ArrayList<List<Integer>>(); //two pointers //set i and move j and k (if sum <0 j++ else k--) for(int i = 0; i<nums.length; i++){ if (i != 0 && nums[i] == nums[i - 1]) continue; //***** int j = i+1; int k = nums.length-1; while(j<k){ if(nums[i] + nums[j] + nums[k] == 0){ List<Integer> temp = new ArrayList<Integer>(); temp.add(nums[i]); temp.add(nums[j]);temp.add(nums[k]); //if(!res.contains(temp)) //why add this make TLE **** res.add(temp); ++j; //System.out.println("wei"); while (j < k && nums[j] == nums[j-1]) ++j; **** }else if(nums[i] + nums[j] + nums[k] < 0){ j++; }else { k--; } } } return res; } }
1.avoid the duplicate elements -1 -1 (for the same values, there are same results)
2. avoid using contains because of O(n), that is the reason why we need check the duplicate elements manually instead of using contains
Solution 2: using hashmap: n^2*lgn
class Solution { public List<List<Integer>> threeSum(int[] nums) { List<List<Integer>> res = new ArrayList<List<Integer>>(); Arrays.sort(nums); for(int i = 0; i < nums.length; i++){ if(i!=0 && nums[i-1] == nums[i]) continue; Set<Integer> set = new HashSet<>(); // no duplicate elements for(int j = i+1; j<nums.length; j++){// nums[j] : b and c means: count all nums[i] as c if(set.contains(-nums[i]-nums[j])){ // c List<Integer> temp = new ArrayList<>(); temp.add(nums[i]);temp.add(nums[j]);temp.add(-nums[i]-nums[j]); res.add(temp); //avoid the duplicate elemnts ++j; while(j < nums.length && nums[j-1]==nums[j]) j++; --j; } if(j<nums.length) set.add(nums[j]); } } return res; } }
hashset
how to using two loop to represent three numbers.
1. treat all nums[j] as c(the third elemnts)
2. As a+b+c = 0, c = -a-b, we need find a and b to satisfy the requirement
*15. 3Sum (three pointers to two pointers), hashset
原文：https://www.cnblogs.com/stiles/p/leetcode15.html