# Three Sum Closest - Leet Code Solution

September 13, 2019

## Problem Statement

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).``````

## Solution-1

The obvious brute force algorithm. The key is to get the closest. You need to compare

``Math.abs(target - calculated_sum)``

## Solution-2

Lets look at the optimized solution.

1. Sort the array
2. Have left and right pointers.
3. Keep calculating sum of three values.
4. Compare absolute value of difference between targetSum and calculated sum.
5. If sum is lesser, need to move left pointer
6. else move right pointer.
``````public int threeSumClosest(int[] nums, int target) {
Arrays.sort(nums);

int l = nums.length;
int minDiff = Integer.MAX_VALUE;
int result = 0;
for (int i=0; i<l; i++) {
int j=i+1;
int k=l-1;

while (j < k) {
int sum = nums[i] + nums[j] + nums[k];
if (sum == target) return sum;
else if (sum < target) j++;
else k--;

if (Math.abs(target - sum) < minDiff) {
minDiff = Math.abs(target - sum);
result = sum;
}
}
}

return result;
}``````

## Similar Posts

### Check whether number is palindrome or not - Leet Code Solution

Problem Statement Determine whether an integer is a palindrome. An integer is a…

### Zigzag Pattern String Conversion - Leet Code Solution

Problem Statement The string “PAYPALISHIRING” is written in a zigzag pattern on…

### Insertion Sort Algorithm

Its a kind of incremental insertion technique, where the algorithm build up…

### Longest Palindrome Substring - Leet Code Solution

Problem Statement Given a string s, find the longest palindromic substring in s…

### Swap Nodes Pairs in Link List - Leet Code Solution

Problem Statement Given a linked list, swap every two adjacent nodes and return…

### Convert Roman to Integer number - Leet Code Solution

Problem Statement Roman numerals are represented by seven different symbols: I…

## Latest Posts

### Leetcode - Rearrange Spaces Between Words

Problem Statement You are given a string text of words that are placed among…

### Leetcode - Maximum Non Negative Product in a Matrix

Problem Statement You are given a rows x cols matrix grid. Initially, you are…

### Leetcode - Split a String Into the Max Number of Unique Substrings

Problem Statement Given a string s, return the maximum number of unique…

### Crawler Log Folder - minimum number of operations needed to go back to the main folder after the change folder operations.

Problem The Leetcode file system keeps a log each time some user performs a…

### Replace all spaces in a string with %20

Problem Statement Replace all spaces in a string with ‘%20’ (three characters…

### Determine if a string has all unique characters

Problem Implement an algorithm to determine if a string has all the characters…