# Question

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]

Could you solve it in O(n^2) runtime?

@tag-array


# Algorithm

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,

# Code

Java

• public class Three_Sum_Smaller {

// time: O(N^2)
// space: O(1)
public class Solution {
public int threeSumSmaller(int[] nums, int target) {

if(nums == null || nums.length == 0) {
return 0;
}

Arrays.sort(nums);

int count = 0;
for(int i = 0; i < nums.length - 2; i++) {
int lo = i + 1, hi = nums.length - 1;
while(lo < hi) {
if(nums[i] + nums[lo] + nums[hi] < target) {
count += hi - lo; // adding a smaller number must also be less than Target value
lo++;
} else {
hi--;
}
}
}

return count;
}
}
}

• // OJ: https://leetcode.com/problems/3sum-smaller/
// Time: O(N^2)
// Space: O(1)
class Solution {
private:
int twoSumSmaller(vector<int>& nums, int start, int target) {
int i = start, j = nums.size() - 1, ans = 0;
while (i < j) {
if (nums[i] + nums[j] < target) {
ans += j - i;
++i;
} else --j;
}
return ans;
}
public:
int threeSumSmaller(vector<int>& nums, int target) {
int N = nums.size(), ans = 0;
sort(nums.begin(), nums.end());
for (int i = 0; i < N; ++i)
ans += twoSumSmaller(nums, i + 1, target - nums[i]);
return ans;
}
};

• class Solution(object):
def threeSumSmaller(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: int
"""
ans = 0
nums.sort()
for i in range(0, len(nums)):
start, end = i + 1, len(nums) - 1
while start < end:
if nums[i] + nums[start] + nums[end] < target:
ans += end - start
start += 1
else:
end -= 1

return ans