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

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

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

推荐阅读：
如何让百度快速收录网页?快用百度站长平台“快速收录”功能！　 php和asp网站源码有什么不同？哪种代码语言更好?　 装修公司网销业绩不好？原因和解决方法都在这里　 亚马逊正式推出企业搜索引擎Kendra　 为什么Google SEO见效慢　 一个三流SEOer从业记录　 网站权重如何提升，掌握以下几点快速提权　 SEO关键词排名该掌握的核心优化技巧　 为何网站内容稳定更新还没有关键词排名？　 图中阴影部分面积是多少平方厘米　
评论列表
添加评论