# HashMap O(N^2 ) solution, but time out, why ?

• I use hashmap to solve this problem. Basic idea is to use a hashMap to store the integer as key and its last index as value. Then iterator through the list to find three elements that sum up to zero. Hash these three values into an integer and store in a hashset so that make sure no duplicate would be added to the result list. I think the algorithm is still O(N ^ 2) but why will it time out? Did I implement anything wrong?

``````public List<List<Integer>> threeSum(int[] nums) {
HashMap<Integer, Integer> map = new HashMap<Integer,Integer>();//key is number, value is index
for(int i =0; i < nums.length; i++){
map.put(nums[i], i);
}
HashSet<Integer> duplicate = new HashSet<Integer>();
for(int i =0; i < nums.length-2; i++){
for(int j = i+1; j < nums.length-1; j++){
int sum = nums[i]+nums[j];
int rest = 0-sum;
if(map.containsKey(rest) && map.get(rest)> j){
int [] sort = new int[3];
sort[0]=nums[i];
sort[1]=nums[j];
sort[2]=rest;
Arrays.sort(sort);
int key = Arrays.hashCode(sort);// hash based on the content of array
if(!duplicate.contains(key)){