Given an array nums of n integers and an integer target, find three integers in nums such that the sum is closest to target. Return the sum of the three integers. You may assume that each input would have exactly one solution.
Example:
Given array nums = [-1, 2, 1, -4], and target = 1. The sum that is closest to the target is 2. (-1 + 2 + 1 = 2).
The straightforward solution has to be the bruteforce algorithm, that exhausts every three numbers using O(N^3) loop – which is obviously too slow.
Two Pointer Algorithm in O(nlogN)
We first need to sort the entire array which takes O(nlogN). Once we have determined the first two numbers in O(N^2), we can search the rest in (logN) as the array is sorted. The following algorithm takes O(n*n*logN).
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 | class Solution { public: int threeSumClosest(vector<int>& nums, int target) { sort(begin(nums), end(nums)); int sum = nums[0] + nums[1] + nums[2]; for (int i = 0; i < nums.size() - 2; ++ i) { for (int j = i + 1; j < nums.size() - 1; ++ j) { int k = nums.size() - 1; while (j < k) { int cur = nums[i] + nums[j] + nums[k]; if (cur == target) { return target; } else if (cur < target) { j ++; } else { k --; } if (abs(cur - target) < abs(sum - target)) { sum = cur; } } } } return sum; } }; |
class Solution { public: int threeSumClosest(vector<int>& nums, int target) { sort(begin(nums), end(nums)); int sum = nums[0] + nums[1] + nums[2]; for (int i = 0; i < nums.size() - 2; ++ i) { for (int j = i + 1; j < nums.size() - 1; ++ j) { int k = nums.size() - 1; while (j < k) { int cur = nums[i] + nums[j] + nums[k]; if (cur == target) { return target; } else if (cur < target) { j ++; } else { k --; } if (abs(cur - target) < abs(sum - target)) { sum = cur; } } } } return sum; } };
However, we don’t need to bruteforce the second number. Once the first number is settled, we can using two pointer algorithm to determine the remainding two numbers. If at anytime, we find a sum that is equal to the target, we immediately return the sum otherwise, we need to iteratively store the minimal sum difference.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 | class Solution { public: int threeSumClosest(vector<int>& nums, int target) { sort(begin(nums), end(nums)); int sum = nums[0] + nums[1] + nums[2]; for (int i = 0; i < nums.size() - 2; ++ i) { int j = i + 1; int k = nums.size() - 1; while (j < k) { int cur = nums[i] + nums[j] + nums[k]; if (cur == target) { return target; } else if (cur < target) { j ++; } else { k --; } if (abs(cur - target) < abs(sum - target)) { sum = cur; } } } return sum; } }; |
class Solution { public: int threeSumClosest(vector<int>& nums, int target) { sort(begin(nums), end(nums)); int sum = nums[0] + nums[1] + nums[2]; for (int i = 0; i < nums.size() - 2; ++ i) { int j = i + 1; int k = nums.size() - 1; while (j < k) { int cur = nums[i] + nums[j] + nums[k]; if (cur == target) { return target; } else if (cur < target) { j ++; } else { k --; } if (abs(cur - target) < abs(sum - target)) { sum = cur; } } } return sum; } };
The optimal algorithm using two pointer algorithm is O(nlogN).
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) —
loading...
Last Post: The Lazy Singleton Design Pattern in Java
Next Post: How to For-Loop and do Math/Arithmetic Operations in Windows/NT Batch - the FizzBuzz Programming Example