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


  • 0
    Z

    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));
                        if(set.add(value) ){
                            List<Integer> tmp = new ArrayList<>();
                            tmp.add(nums[i]);
                            tmp.add(nums[j]);
                            tmp.add(nums[key]);
                            r.add(tmp);
                        }
                        
                    }
                }
            }
            return r;
        }
    

  • 0
    F

    it cannot pass? It gets Time Limit Exceeded now


  • 0
    Z

    @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)


  • 0
    F

    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.


  • 0
    Z

    @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!


  • 0
    F

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


  • 0
    Z

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


Log in to reply
 

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