Help! How to handle the special case 0 ?


  • 0
    Y
    public class Solution {
    public ArrayList<ArrayList<Integer>> threeSum(int[] num) {
        ArrayList<ArrayList<Integer>> result = new ArrayList<>();
        Arrays.sort(num); // first sort the array
        if(num.length>0){
        int former = num[0];
        if(former>0 || num.length<3){ // the length is less than 3 or the first element>0 return
            return result;
        }
        Set<ArrayList<Integer>> Test_dup = new HashSet<>(); // avoid duplicate
        for(int i=1;i<num.length;i++){
             int sum = former + num[i];
             if(sum<0){
                 int index = Arrays.binarySearch(num,-sum); // try to find the index using binarySearch
                 if(index>=0){
                     ArrayList<Integer> elements = new ArrayList<>();
                     elements.add(former);
                     elements.add(num[i]);
                     elements.add(num[index]);
                     if(!Test_dup.contains(elements)){
                         result.add(elements);
                     }
                     Test_dup.add(elements);
                 }
             }
            former = num[i];
        }
        }
        return result;
    }
    

    }


  • 0
    I

    Hi, Yuzhen,

    I didn't go through your code, but I had the same problem and managed to solve it. I'm sharing my solution and it may help you.

    The problem is with binarySearch. The binary search returns immediately when it finds a match. It works fine if the integers are unique. But if there are duplicates then it creates problem. We actually need the binarySearch to return the highest index in the array that has the match, not just the first index where it finds a match: So, we need to keep looking if there is still matches beyond the first match. A slight change in the code when it finds the mach solves this probelm. Something like:

    if (arry[mid] == target) { out = mid; low = mid+1; }... return out;


Log in to reply
 

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