"Solution" using hashset Java


  • 0
    E

    A common follow up for this problem is without using sort. So I wrote this solution just to illustrate my idea.

    This solution cannot pass the OJ due to TLE. But it did pass 300+ test cases, also since its a bit different from other ideas, I thought I can still share it.

    Basically, we want to find three numbers, such that a + b + c = 0 and the order of indexes are index(a) < index(b) < index(c), my idea is to enumerate the middle number b, and add it to hashset after visiting it. The hashset is for quick finding c. Enumerating the middle number b guarantee the the order of index which is index(a) < index(b) < index(c).

    Also, to avoid duplicate result, we need to generate a key for current result, and see if it already exits.

    public class Solution {
        public List<List<Integer>> threeSum(int[] nums) {
            List<List<Integer>> res = new ArrayList<List<Integer>>();
            if(nums == null || nums.length < 3) return res;
            
            Set<Integer> set = new HashSet<>();
            Set<String> visited = new HashSet<>();
            
            for(int j = nums.length - 1 ; j >= 0 ; j--){
                for(int i = j - 1 ; i >= 0 ; i--){
                    int a = nums[i], b = nums[j];
                    int c = 0 - a - b;
                    if(set.contains(c)) {
                        String key = getKey(a,b,c);
                        if(!visited.contains(key)){
                            res.add(Arrays.asList(a,b,c));
                            visited.add(key);
                        }
                    }
                }
                set.add(nums[j]);
            }
            return res;
        }
        
        public String getKey(int a, int b, int c){
            int max = Math.max(a,Math.max(b,c));
            int min = Math.min(a,Math.min(b,c));
            int sum = a + b + c;
            return max + "," + (sum - max - min) + "," + min;
        }
    }
    

Log in to reply
 

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