How to Find the Closest Sum of Three in an Array using Two Point

  • 时间：2020-09-25 11:32:47
  • 分类：网络文摘
  • 阅读：108 次

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

–EOF (The Ultimate Computing & Technology Blog) —

推荐阅读：
周末妈妈从家送巧巧去学校学钢琴　 平角就是一条直线判断对错　 29957四舍五入到百位、千位、万位是多少？　 已知被除数，除数，商与余数的和是235，已知商是27，余数是6，求除数。　 图中几条直线、几条射线、几条线段？　 滞尘是什么意思？　 冬冬是2008年2月29日出生的，到2016年2月29日他一共过了几个生日？　 饮料架上放有大、中、小三种包装的饮料　 有一架天平和一个50克的砝码，如果要得到150克糖果　 看似容易－六年级易错题集锦　
评论列表
添加评论