dimanche 24 janvier 2016

3SUM: avoid duplicates

To avoid duplicates I use an if-clause in the while loop, and I was wondering why this does not work. Thanks!

public List<List<Integer>> threeSum(int[] nums) {
    List<List<Integer>> result = new ArrayList<List<Integer>>();
    Arrays.sort(nums);

    for (int i = 0; i<nums.length; i++){
        if (i > 0 && nums[i] == nums[i-1]){
            continue;
        }
        int target = -1*nums[i];
        int start = i+1;
        int end = nums.length-1;

        while (start < end){

            if (nums[start] == nums[start+1]){
                start++;
            } 

            if (nums[end] == nums[end--]){
                end--;
            } 

            if (nums[start]+nums[end] == target){
                System.out.printf("found");
                List<Integer> temp = new ArrayList<Integer>();
                temp.add(nums[i]);
                temp.add(nums[start]);
                temp.add(nums[end]);
                result.add(temp);
                start++;
                end--;
            } else if (nums[start]+nums[end] < target) {
                start++;
            } else {
                end--;
            }
        }
    }
    return result;

I was testing on [-1,0,1] and my code returned an empty list. I tried to debug and printed some messages, and it seems that when i=1, in the while loop, it first enters

if (nums[start] == nums[start+1]){
                start++;
} 

But nums[start] does not equal to nums[start+1] when start=1. This is quite bizzare. Can someone explain it to me?

Aucun commentaire:

Enregistrer un commentaire