What's wrong?


  • 0
    S

    I tried with another method but when it comes to the last test cases, it doesn't work correctly.

    In my method, I do the following jobs:

    1.sort the array.
    2.devide the sorted array to three parts: negative, zero, positive.
    3.In order to get a sum of zero, there are four conditions:
    (1)two negative and one positive, like [-2, -1, 3]
    (2)two positive and one negative, like [-3, 1, 2]
    (3)one negative, one positive and a zero, like [-1, 0, 1]
    (4)three zeros.

    The time cost is O(n^2) and the space is O(n).
    May it be so good as the methods posted here, I just want to know why it does not work correctly. Thank you.

    public class Solution {
        public List<List<Integer>> threeSum(int[] nums) {
            List<List<Integer>> result = new ArrayList<List<Integer>>();
            List<List<Integer>> myresult = new ArrayList<List<Integer>>();
            if(nums.length < 3) return result;
            Arrays.sort(nums);
            int cntzero = countZero(nums);
            if(cntzero >= 3){
                result.add(Arrays.asList(0, 0, 0));
            }
            int negaend = -1;
            int posistart = -1;
            if(nums[0] >= 0 || nums[nums.length - 1] <= 0){
                return result;
            }
            for(int i = 0; i < nums.length; i++){
                //devide the array into three parts: negative, 0, positive
                if(nums[i] >= 0 && negaend == -1) negaend = i - 1;
                if(nums[i] > 0 && posistart == -1) posistart = i;
            }
            
            //convert each part into hashmap
            Map<Integer, Integer> negamap = array2map(nums, 0, negaend);
            Map<Integer, Integer> posimap = array2map(nums, posistart, nums.length - 1);
            
    
            //find a positive using two negative,cost:O(n^2)
            for(int i = 0; i <= negaend - 1; i++){
                for(int j = i + 1; j <= negaend; j++){
                    int sum = nums[i] + nums[j];
                    if(posimap.containsKey(0 - sum)){
                        result.add(Arrays.asList(nums[i], nums[j], 0 - sum));
                    }
                }
            }
            
            //find a negative using two positive, cost:O(n^2)
            for(int i = posistart; i < nums.length - 1; i++){
                for(int j = i + 1; j < nums.length; j++){
                    int sum = nums[i] + nums[j];
                    if(negamap.containsKey(0 - sum)){
                        result.add(Arrays.asList(nums[i], nums[j], 0 - sum));
                    }
                }
            }
            
            //if there is zeros, find one positive and one negative that have a sum of zero, cost:O(n)
            if(cntzero > 0){
                for(int i = 0; i <= negaend; i++){
                    if(posimap.containsKey(0 - nums[i])){
                        result.add(Arrays.asList(nums[i], 0, 0 - nums[i]));
                    }
                }
            }
            for(List<Integer> list : result){
            	Collections.sort(list);
            	if(!existsin(list, myresult)){
            		myresult.add(list);
            	}
            }
            
            return myresult;
        }
        //convert each part into hashmap, costs:O(n)
        private Map<Integer, Integer> array2map(int[] nums, int begin, int end){
            Map<Integer, Integer> map = new HashMap<Integer, Integer>();
            for(int i = begin; i <= end; i++){
                if(!map.containsKey(nums[i]))map.put(nums[i], 0);
            }
            return map;
        }
        //count the number of zero, costs:O(n)
        private int countZero(int[] nums){
            int cnt = 0;
            for(int i : nums){
                if(i == 0)cnt++;
            }
            return cnt;
        }
        
        private boolean existsin(List<Integer> list, List<List<Integer>> lists){
        	for(List<Integer> savedlist : lists){
        		if(list.get(0) == savedlist.get(0) && list.get(1) == savedlist.get(1) && list.get(2) == savedlist.get(2))
        			return true;
        	}
        	return false;
        }
    }
    

Log in to reply
 

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