https://leetcode.com/problems/3sum-closest/

// At first, my DP solution exceeds time limitation

// Then with the hint fo the discussion board,

// I have the final solution of impl2,

// which is very smart!

 

class Solution {    map
     
      
       >, int> mp;    int diff(int a, int b) {        return a>=b ? a-b : b-a;    }        bool close(int a, int b) {        if (b == 0) {            // for init condition            return true;        }                if (a < 0) {            a *= -1;        }        if (b < 0) {            b *= -1;        }        return a < b;    }        vector
       
         nums;    public:    int threeSumClosest(vector
        
         & n, int target) {        nums = n;                int vlen = nums.size();        if (vlen < 3) {            return 0;        }                //return impl(target, vlen, 3);        return impl2(target, vlen);    }        int impl2(const int &target, const int &end) {        sort(nums.begin(), nums.end());        // can be 0, as if 0 returns asap        int df = 0;        int n;                int p;        int q;        int ndf;        for (int i = 0; i < end-2; i++) {            n = nums[i];            p = i + 1;            q = end - 1;            while (p < q) {                ndf = n + nums[p] + nums[q];                if (ndf == target) {                    return target;                }                else if (ndf > target) {                    q--;                }                else {                    p++;                }                if (close(ndf - target, df)) {                    df = ndf - target;                }            }        }        return target + df;    }        // below solution exceed time limit    int impl(const int &target, const int &end, const int &sz) {        if (sz == 0 || end == 0) {            return 0;        }                pair
         
          > pr = make_pair(target, make_pair(end, sz));        if (mp.find(pr) != mp.end()) {            return mp[pr];        }                int ret;        int df;                if (sz == 1) {                        ret = nums[0];            df = diff(ret, target);                        for (int i=1; i
          
           >, int> mp; int diff(int a, int b) { return a>=b ? a-b : b-a; } bool close(int a, int b) { if (b == 0) { // for init condition return true; } if (a < 0) { a *= -1; } if (b < 0) { b *= -1; } return a < b; } vector
           
             nums; public: int threeSumClosest(vector
            
             & n, int target) { nums = n; int vlen = nums.size(); if (vlen < 3) { return 0; } //return impl(target, vlen, 3); return impl2(target, vlen); } int impl2(const int &target, const int &end) { sort(nums.begin(), nums.end()); // can be 0, as if 0 returns asap int df = 0; int n; int p; int q; int ndf; for (int i = 0; i < end-2; i++) { n = nums[i]; p = i + 1; q = end - 1; while (p < q) { ndf = n + nums[p] + nums[q]; if (ndf == target) { return target; } else if (ndf > target) { q--; } else { p++; } if (close(ndf - target, df)) { df = ndf - target; } } } return target + df; } // below solution exceed time limit int impl(const int &target, const int &end, const int &sz) { if (sz == 0 || end == 0) { return 0; } pair
             
              > pr = make_pair(target, make_pair(end, sz)); if (mp.find(pr) != mp.end()) { return mp[pr]; } int ret; int df; if (sz == 1) { ret = nums[0]; df = diff(ret, target); for (int i=1; i
              

& nums, int target, int len) { if (len == 0) { return 0; } int vlen = nums.size(); if (vlen < len) { return 0; } int i= 0; int result = 0; if (vlen == len) { for (i=0; i

len) { nums.pop_back(); result = sumClosest(nums, target, len); nums.push_back(tail); } nums.pop_back(); int ret = sumClosest(nums, target-tail, len-1) + tail; nums.push_back(tail); int diff1 = target - result; diff1 = (diff1>0)?diff1:diff1*-1; int diff2 = target - ret; diff2 = (diff2>0)?diff2:diff2*-1; if(diff1 < diff2) { return result; } return ret; }