AC O(n^2) Java solution

• ``````public int threeSumSmaller(int[] nums, int target) {
int len = nums.length;
if(len < 3) return 0;
Arrays.sort(nums);
int count = 0;
for(int i=0; i<nums.length-2; i++) {
int j = i + 1;
while(j < len && nums[i] + 2 * nums[j] < target) {
j++;
}
j--;				// any two elements within i to j will satisfy the condition
count += (j-i-1)*(j-i)/2;
for(int k=j+1; k<len; k++) {        // k go up, j go down
while(j > i && nums[i] + nums[j] + nums[k] >= target) {
j--;
}
count += j-i;
}
}
return count;
}
``````

We already know that any two elements from i to j along with i itself is added to our count, now we need to go up to see if there's more triplets when one element is bigger than nums[j]. So we let k start from j+1 to len and let j decrement to i. In each position, we check if current j and k satisfy the condition. If it does, that means all elements between i and current j along with current k can be added to the count. Then we can increment k to see if current j still satisfy the condition. If it doesn't, we decrement j until it does.

So for each i, the runtime is O(n) because we at most access each position twice (once when we find the appropriate j, another when j decrement all the way down from that position), thus the total runtime is O(n^2).

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