# java solution without sort. Not fast, 89ms, but with a O(n^2) time complexity

• I just used hashmap to reduce O(n^3) to O(n^2), and used a "histogram" like set to avoid duplicate. You may further optimize this code using similar idea if you do not want sort.

``````public List<List<Integer>> threeSum(int[] nums) {
List<List<Integer>> r = new ArrayList<>();
HashMap<Integer,Integer> map = new HashMap<Integer,Integer>();
Set<Double> set = new HashSet<Double>();
int l=nums.length;
int min=0;
for(int i=0;i<l;i++){
min=min<nums[i]?min:nums[i];
map.put(-nums[i],i);
}
for(int i=0;i<l-1;i++){
for(int j=i+1;j<l;j++){

Integer key=map.get(nums[i]+nums[j]);
if(key!=null && key!=i && key!=j){
double value=(1<<(nums[i]-min))+(1<<(nums[j]-min))+(1<<(nums[key]-min));
List<Integer> tmp = new ArrayList<>();
}

}
}
}
return r;
}
``````

• it cannot pass? It gets Time Limit Exceeded now

• @forestwn , yes I know this would happen, if try to submit again, it will be accepted. As I said it's slow, but with O(n^2)

• I tried many times it still cannot pass. Anyway thanks for your nice idea! The point is to find a way to encode 3 numbers and store the code in set.

• @forestwn yes, you got the idea. I previously successfully submitted this code, but I know it's on the boundary and I haven't optimized it yet. However, this "coding" could run into problems if the given number in the list is too big(e.g. Larger than 64). I haven't found a better coding scheme yet. But yes, encoding the 3 numbers into a unique number is the key idea. Thanks!

• @zhaoyuac09 I find a feasible way. Encode it like "1#5#6" in sorted. string is useful when hash is needed

• @forestwn that's a good way. I used this in 4 sum question, however, still time limit exceeded

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.