259. 3Sum Smaller
Explanation:
This problem asks us to find the number of triplets in an array whose sum is less than a given target. We can solve this problem using a two-pointer approach.
- Sort the array in non-decreasing order.
- Initialize a count variable to 0.
- Iterate over the array with a fixed index
iand use two pointersleftandrightto find the pairs that sum up to less than the target. - If the sum of nums[i] + nums[left] + nums[right] is less than the target, then all the numbers between left and right form valid pairs as well.
- Increment the count by
right - leftand move the left pointer to the right. - If the sum is greater than or equal to the target, decrement the right pointer.
- Repeat steps 4-6 until the left pointer crosses the right pointer.
- Return the final count.
: :
class Solution {
public int threeSumSmaller(int[] nums, int target) {
Arrays.sort(nums);
int count = 0;
for (int i = 0; i < nums.length - 2; i++) {
int left = i + 1, right = nums.length - 1;
while (left < right) {
int sum = nums[i] + nums[left] + nums[right];
if (sum < target) {
count += right - left;
left++;
} else {
right--;
}
}
}
return count;
}
}Code Editor (Testing phase)
Improve Your Solution
Use the editor below to refine the provided solution. Select a programming language and try the following:
- Add import statement if required.
- Optimize the code for better time or space complexity.
- Add test cases to validate edge cases and common scenarios.
- Handle error conditions or invalid inputs gracefully.
- Experiment with alternative approaches to deepen your understanding.
Click "Run Code" to execute your solution and view the output. If errors occur, check the line numbers and debug accordingly. Resize the editor by dragging its bottom edge.