Formatted question description: https://leetcode.ca/all/259.html
259 3Sum Smaller 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 O(n^2) runtime? @tag-array
The follow up in the title allows us to achieve it within
O(n^2) time complexity. Then learn from the methods in the previous two questions
3Sum Closest and
3Sum, and use double pointers to do it.
There is a trick here that is to judge When the sum of three numbers is less than the target value, right-left should be added to the result at this time, because after the array is sorted, if the addition of num[right] is less than the target value, then adding a smaller number must also be less than Target value, then move the left pointer to the right by one place, otherwise move the right pointer to the left by one place,