Accepted java solution beats 100% with explanations


  • 0
    J
    • Make another array 'amountOf' to store each amount of numbers in nums.
    • Handle some special inputs: min in nums > 0, max in nums < 0
    • Add possible triplet [0,0,0] in result list, and we only deal with [x,z,y] where (x<0 and y>0) in the next step.
    • Create two methods of getting next element existed in nums for passing x<0 and y>0
    • Loop to find every triplet [x,z,y] making x+z+y==0
        public List<List<Integer>> threeSum(int[] nums) {
            
            ArrayList list = new ArrayList();
            
            // Easy sort the array, faster than bubble sort 
            Arrays.sort(nums);
    
            if (nums.length<3) return list;        
    
            // nums[0] is the min in nums, nums[nums.length-1] is the max in nums
            // l means how many different numbers in nums
            int l = nums[nums.length-1]-nums[0]+1;
            int[] amountOf = new int[l];
            // Take the amount of the min number (nums[0]) as the first element in amountOf
            // amountOf[i] means how many times the number 'i' appears in nums, and i is not in nums if amountOf[i] equals to 0
            for (int i=0; i<nums.length; i++) amountOf[nums[i]-nums[0]]++;
            
            int zero = -nums[0];
            // zero<0 means min in nums > 0, zero>=amountOf.length means max in nums < 0
            if (zero<0 || zero>=amountOf.length) return list;
            
            // Add possible triplet [0,0,0]
            if (amountOf[zero]>=3) list.add(new int[]{0,0,0});
            
            // double loop to pass every [x,z,y] where x<0 and y>0
            for (int x=0; x<zero; x=foreward(amountOf,x)) {
                for (int y=amountOf.length-1; y>zero; y=backward(amountOf,y)) {
                    int z = 3*zero-x-y;
                    // [x,z,y] found!
                    if (z==x && amountOf[x]>=2 || z==y && amountOf[y]>=2 || z>x && z<y && amountOf[z]>=1)
                        list.add(new int[]{x-zero,z-zero,y-zero});
                }
            }
    
            return list;
        }
        
        // find next number < y
        public int backward(int[] amountOf,int y) {
            for (--y;y>=0;--y) {
                if (amountOf[y]>0) return y;
            }
            return y;
        }
        
        // find next number > x
        public int foreward(int[] amountOf,int x) {
            for (++x;x<amountOf.length;++x) {
                if (amountOf[x]>0) return x;
            }
            return x;
        }
    

Log in to reply
 

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