Given an array of

*n*integers*nums*and a*target*, find the number of index triplets`i, j, k`

with `0 <= i < j < k < n`

that satisfy the condition `nums[i] + nums[j] + nums[k] < target`

.
For example, given

*nums*=`[-2, 0, 1, 3]`

, and *target*= 2.
Return 2. Because there are two triplets which sums are less than 2:

[-2, 0, 1] [-2, 0, 3]

Follow up:

Could you solve it in

Could you solve it in

*O*(*n*2) runtime?**Understand the problem:**

The problem looks quite similar to the 3-sum. Thus we could still sort the array first and use two pointers.

The only thing needs to take special care of is how to move the pointers. There are two cases to handle:

-- If A[i] + A[j] + A[k] < target, which means the numbers between j and k are all less than target, because the array is sorted. Then we move the j pointer forward.

-- If A[i] + A[j] + A[k] >= target, we move k pointer backward.

**Code (Java):**

public class Solution { public int threeSumSmaller(int[] nums, int target) { if (nums == null || nums.length < 3) { return 0; } int result = 0; Arrays.sort(nums); for (int i = 0; i < nums.length - 2; i++) { int j = i + 1; int k = nums.length - 1; while (j < k) { if (nums[i] + nums[j] + nums[k] < target) { result += (k - j); j++; } else { k--; } } } return result; } }

Why you used result += (k - j) instead of just result++ ?

ReplyDeleteCan you explain the logic ?

If A[i] + A[j] + A[k] < target, which means the numbers between j and k are all less than target, because the array is sorted. Then we move the j pointer forward.

DeleteIf it's less then the target, then that means it needs to be accounted for when you update the result count. If you don't, the algorithm won't hit those cases.

This comment has been removed by the author.

ReplyDeleteThis comment has been removed by the author.

DeleteArrays.sort(array);

ReplyDeletefor(int i = 0 ; i=target){

break;

}

for(int j = i+1;j<array.length;j++){

for(int k=j+1;k<array.length;k++){

count++;

sum=0;

sum= array[i]+array[j]+array[k];

if(sum < target){

System.out.println("["+array[i]+","+array[j]+","+array[k]+"]");

}else{

break;

}

}// K

}// J

}// I

System.out.println("count:"+count);

You can't sort. i < j < k .. means you need to retain the order of the indices! A more "brute force solution" with a duplicate removal mechanism is required.

ReplyDelete