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

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

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

推荐阅读：
奥数题:一份工作按计划的时间算　 简便计算题：1997÷(1997+1997/1998)+(1/1999)　 数学题:在比例尺1：5000的图纸上　 2014年是平年还是闰年　 数学题:在11次红灯变绿灯之间的黄灯亮起中　 奥数题:从这两堆煤中分别运走同样的吨数后　 数学题:用4cm长的线段表示实际距离1200km　 数学题:一根圆柱形木头小明的爸爸将它锯成4段　 奥数题:当王明在100m赛跑冲到终点时，领先刘铭10m　 数学题:小敏要买一些圣诞卡　
评论列表
添加评论