[Leetcode] 3Sum Closest

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

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

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

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

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

 

  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。

 

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