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 runtime?
Solution: Two Pointers
class Solution(object):
def threeSumSmaller(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: int
"""
nums.sort()
count = 0
for idx, num in enumerate(nums):
low = idx + 1
high = len(nums) - 1
while low < high:
s = num + nums[low] + nums[high]
if s < target:
count += high - low
low += 1
else:
high -= 1
return count