[Leetcode] 3Sum Closest

連假閒來沒事,想說維持一下腦力,終於又寫了幾題leetcode (睽違一年多XDD)

這個算總和的題目前面好像有幾個類似題,之前印象有寫過3Sum的題目

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

所以就看了一年多前那題解法是怎樣,然後一樣畫葫蘆稍微改一下就寫好這題惹

code還蠻醜的,discuss裡面code應該都精簡到一個不行QQ

class Solution {
public:
    int threeSumClosest(vector<int>& nums, int target) {
        sort(nums.begin(),nums.end());//nlogn
        
        int len = nums.size();//n
        int sec_target , low , high, min_diff=INT_MAX;
        
        int ans = 0;
        
        for(int i = 0 ; i < len ; i++) //n^2
        {
            if(i == 0 || nums[i-1] != nums[i])
                sec_target = target-nums[i]; //(t-c)
            else
                continue;
            
            low = i + 1 ; high = len - 1;
            
            while(low < high)
            {
                if (abs(sec_target,(nums[low] + nums[high])) < min_diff)
                {
                    min_diff = abs(sec_target,(nums[low] + nums[high]));
                    ans = nums[low] + nums[high] + nums[i];
                }
                
                if(nums[low] + nums[high] < sec_target)
                    low++;
                else
                    high--;
 
            }
            
        }
        
        return ans;
    }
    
    int abs(int a , int b)
    {
        if(a > b)
            return a-b;
        else
            return b-a;
    }
};

 

  1. 跟3sum精神一樣,先sort。
  2. 跟3sum精神一樣,3sum的題目是a+b+c=t,先假設c為array[i],然後另a,b分別array[i+1],array[len-1]。(用最小跟最大值去逼近target)
  3. 跟3sum精神一樣,把題目看成a+b=t-c,把t-c看成一個新的target,目標使找到適合的a,b,如果a+b>t-c,代表b太大了,讓b往前退一格。反之則讓a往後進一格。
  4. 不一樣的地方在,3sum題目要使 a+b 完全等於 t-c,而這裡我們要找min diff,這邊diff是指a+b與t-c的差值,因為closest的就是要diff最小的,所以發現diff更小了就更新目前的answer。

 

然後我一直唸成三傻,讓我想到冰與火的傻姍