Two Pointer Algorithm to Count the Sum of Three Numbers Less than Target

Given a list of integers nums and an integer target, return the number of triples i < j < k that exist such that nums[i] + nums[j] + nums[k] < target.

Constraints
n ≤ 1,000 where n is the length of nums
Example 1
Input
nums = [-3, 5, 3, 2, 7]
target = 9
Output
5
Explanation
Here are the different triples’ values:
-3 + 5 + 3 = 5
-3 + 5 + 2 = 4
-3 + 3 + 2 = 2
-3 + 3 + 7 = 7
-3 + 2 + 7 = 6

Sort and Two Pointer Algorithm to Count Sum of Three Numbers Less than Target

Firt, we sort the array by taking the cost O(NLogN). Then we iterate for the first number, and use two pointers to determine the second and third number. If the current sum is less than target, we have to accumulate the answer by the difference between two pointers, and increment the lower pointer. Otherwise, we have to decrement the higher pointer.

The complexity is O(N^2) quadric.

1
2
3
4
5
6
7
8
9
10
11
12
13

class Solution:
    def countSumOfThreeNumbersLessThanTarget(self, nums, target):
        nums.sort()
        ans = 0
        for i in range(len(nums)):
            j, k = i + 1, len(nums) - 1
            while j < k:
                if nums[i] + nums[j] + nums[k] < target:
                    ans += k - j
                    j += 1
                else:
                    k -= 1
        return ans

class Solution:
    def countSumOfThreeNumbersLessThanTarget(self, nums, target):
        nums.sort()
        ans = 0
        for i in range(len(nums)):
            j, k = i + 1, len(nums) - 1
            while j < k:
                if nums[i] + nums[j] + nums[k] < target:
                    ans += k - j
                    j += 1
                else:
                    k -= 1
        return ans

Python Two Pointer Algorithm to Count the Sum of Three Numbers Less than Target:

1
2
3
4
5
6
7
8
9
10
11
12
13

class Solution:
    def countSumOfThreeNumbersLessThanTarget(self, nums, target):
        nums.sort()
        ans = 0
        for i in range(len(nums)):
            j, k = i + 1, len(nums) - 1
            while j < k:
                if nums[i] + nums[j] + nums[k] < target:
                    ans += k - j
                    j += 1
                else:
                    k -= 1
        return ans

class Solution:
    def countSumOfThreeNumbersLessThanTarget(self, nums, target):
        nums.sort()
        ans = 0
        for i in range(len(nums)):
            j, k = i + 1, len(nums) - 1
            while j < k:
                if nums[i] + nums[j] + nums[k] < target:
                    ans += k - j
                    j += 1
                else:
                    k -= 1
        return ans

Space requirement is O(1) constant.

See: How to Find the Closest Sum of Three in an Array using Two Pointer Algorithm? (3Sum Closest)

Two Sum Variation Problems

• Teaching Kids Programming - Two Sum in Binary Search Tree via Inorder and Two Pointer Algorithm
• Teaching Kids Programming - Count Pairs Whose Sum is Less than Target (Two Pointer Algorithm)
• Teaching Kids Programming - Sum of Two Numbers Less Than Target using Two Pointer Algorithm
• Teaching Kids Programming - Two Pointer Algorithm to Solve Four Sum Problem
• Teaching Kids Programming - Recursive Algorithm to Find the Sum of Two Numbers in BSTs
• Two Pointer Algorithm to Count the Sum of Three Numbers Less than Target
• Recursive and Two Pointer Algorithms to Determine Four Sum
• Algorithms to Check Sum of Two Numbers in Binary Search Trees
• Teaching Kids Programming - 3 Different Approaches to Solve Two-Sum Problem
• How to Design a Two-Sum Data Structure?
• How to Find the Closest Sum of Three in an Array using Two Pointer Algorithm? (3Sum Closest)
• Teaching Kids Programming - Three Sum Algorithm
• Teaching Kids Programming – Two Sum Algorithm when Input Array is Sorted
• Teaching Kids Programming – Two Sum Algorithm
• Two Pointer Algorithm to Find Maximum Two Sum Less Than K
• The Two Sum Algorithm using HashMap in C++/Java

–EOF (The Ultimate Computing & Technology Blog) —