no. </strong></p>
<ul>
<li>Hardness: \(\color{orange}\textsf{Medium}\)</li>
<li>Ralated Topics: <code>Array</code>、<code>Two Pointers</code>、<code>Sorting</code></li>
</ul>
<hr>
<h3 id="一題目">一、題目<a hidden class="anchor" aria-hidden="true" href="#一題目">#</a></h3>
<p>Given an integer array <code>nums</code> of length <code>n</code> and an integer <code>target</code>, find three integers in <code>nums</code> such that the sum is closet to <code>target</code>.<br>
Return *the sum of the three integers`.<br>
You may assume that each input would have exactly one solution.</p>
<p><strong>Example 1:</strong></p>
<ul>
<li><strong>Input:</strong> nums = [-1,2,1,-4], target = 1</li>
<li><strong>Output:</strong> 2</li>
<li><strong>Explanation:</strong> The sum that is closet to the target is 2. (-1 + 2 + 1 = 2).</li>
</ul>
<p><strong>Example 2:</strong></p>
<ul>
<li><strong>Input:</strong> nums = [0,0,0], target = 1</li>
<li><strong>Output:</strong> 0</li>
<li><strong>Explanation:</strong> The sum that is closet to the target is 0. (0 + 0 + 0 = 0).</li>
</ul>
<p><strong>Constraints:</strong></p>
<ul>
<li><code>3 <= nums.length <= 500</code></li>
<li><code>-1000 <= nums[i] <= 1000</code></li>
<li><code>-10^4 <= target <= 10^4</code></li>
</ul>
<hr>
<h3 id="二分析">二、分析<a hidden class="anchor" aria-hidden="true" href="#二分析">#</a></h3>
<ul>
<li>若用暴力解求解的話，時間複雜度為 \(O(n^3)\)。</li>
<li>故我們可以嘗試先進行排序來簡化問題，時間複雜度為\(O(n\log n)\)。</li>
<li>此題因為是找最接近的，所以無法用 HashMap 解。</li>
<li>使用 Two Pointer，並藉由比較和與 <code>target</code> 的差值來找到最接近的解。</li>
</ul>
<h3 id="三解題">三、解題<a hidden class="anchor" aria-hidden="true" href="#三解題">#</a></h3>
<h4 id="1-two-pointer">1. Two Pointer<a hidden class="anchor" aria-hidden="true" href="#1-two-pointer">#</a></h4>
<ul>
<li>Time complexity: \(O(n^2)\)</li>
<li>Space complexity: \(O(1)\)</li>
</ul>
<div class="highlight"><pre tabindex="0" style="color:#f8f8f2;background-color:#272822;-moz-tab-size:4;-o-tab-size:4;tab-size:4;"><code class="language-C++" data-lang="C++"><span style="display:flex;"><span><span style="color:#66d9ef">int</span> <span style="color:#a6e22e">threeSumCloset</span>(vector<span style="color:#f92672"><</span><span style="color:#66d9ef">int</span><span style="color:#f92672">>&</span> nums, <span style="color:#66d9ef">int</span> target) {
</span></span><span style="display:flex;"><span> <span style="color:#66d9ef">int</span> res <span style="color:#f92672">=</span> INT_MAX;
</span></span><span style="display:flex;"><span> <span style="color:#66d9ef">int</span> n <span style="color:#f92672">=</span> nums.size();
</span></span><span style="display:flex;"><span> <span style="color:#66d9ef">if</span> (n <span style="color:#f92672">==</span> <span style="color:#ae81ff">3</span>) <span style="color:#66d9ef">return</span> accumulate(nums.begin(), nums.end(), <span style="color:#ae81ff">0</span>); <span style="color:#75715e">// 當 n = 3 時，這三個值必為解。
</span></span></span><span style="display:flex;"><span><span style="color:#75715e"></span> sort(nums.begin(), nums.end()) <span style="color:#75715e">// 排序
</span></span></span><span style="display:flex;"><span><span style="color:#75715e"></span> <span style="color:#66d9ef">for</span> (<span style="color:#66d9ef">int</span> i <span style="color:#f92672">=</span> <span style="color:#ae81ff">0</span>; i <span style="color:#f92672"><</span> n<span style="color:#f92672">-</span><span style="color:#ae81ff">2</span>; i<span style="color:#f92672">++</span>) {
</span></span><span style="display:flex;"><span> <span style="color:#66d9ef">int</span> left <span style="color:#f92672">=</span> i<span style="color:#f92672">+</span><span style="color:#ae81ff">1</span>, right <span style="color:#f92672">=</span> n<span style="color:#f92672">-</span><span style="color:#ae81ff">1</span>;
</span></span><span style="display:flex;"><span> <span style="color:#66d9ef">while</span> (left <span style="color:#f92672"><</span> right) {
</span></span><span style="display:flex;"><span> <span style="color:#66d9ef">int</span> sum <span style="color:#f92672">=</span> nums[i] <span style="color:#f92672">+</span> nums[left] <span style="color:#f92672">+</span> nums[right];
</span></span><span style="display:flex;"><span> <span style="color:#66d9ef">if</span> (abs(res <span style="color:#f92672">-</span> target) <span style="color:#f92672">></span> abs(sum <span style="color:#f92672">-</span> target))
</span></span><span style="display:flex;"><span> res <span style="color:#f92672">=</span> sum;
</span></span><span style="display:flex;"><span> <span style="color:#66d9ef">if</span> (sum <span style="color:#f92672">></span> target) {
</span></span><span style="display:flex;"><span> right<span style="color:#f92672">--</span>;
</span></span><span style="display:flex;"><span> } <span style="color:#66d9ef">else</span> <span style="color:#66d9ef">if</span> (sum <span style="color:#f92672"><</span> target) {
</span></span><span style="display:flex;"><span> left<span style="color:#f92672">++</span>;
</span></span><span style="display:flex;"><span> } <span style="color:#66d9ef">else</span> {
</span></span><span style="display:flex;"><span> <span style="color:#66d9ef">return</span> sum; <span style="color:#75715e">// 差值等於 0 時，不會再有更小的差值
</span></span></span><span style="display:flex;"><span><span style="color:#75715e"></span> }
</span></span><span style="display:flex;"><span> }
</span></span><span style="display:flex;"><span> }
</span></span><span style="display:flex;"><span> <span style="color:#66d9ef">return</span> res;
</span></span><span style="display:flex;"><span>}
</span></span></code></pre></div><p><a href="/leetcode">回目錄 Catalog</a></p>
</div>
<footer class="post-footer">
<ul class="post-tags">
<li><a href="https://intervalrain.github.io/tags/leetcode/">Leetcode</a></li>
</ul>
<nav class="paginav">
<a class="prev" href="https://intervalrain.github.io/leetcode/15/">
<span class="title">« 上一頁</span>
<br>
<span>[LeetCode] 15. 3Sum</span>
</a>
<a class="next" href="https://intervalrain.github.io/leetcode/17/">
<span class="title">下一頁 »</span>
<br>
<span>[LeetCode] 17. Letter Combinations of a Phone Number</span>
</a>
</nav>
</footer><script src="https://utteranc.es/client.js"
repo="Reid00/hugo-blog-talks"
issue-term="pathname"
label="Comment"
theme="github-light"
crossorigin="anonymous"
async>
</script>
</article>
</main>
<footer class="footer">
<span>© 2024 <a href="https://intervalrain.github.io/">Rain Hu's Workspace</a></span> ·
<span>
Powered by
<a href="https://gohugo.io/" rel="noopener noreferrer" target="_blank">Hugo</a> &
<a href="https://github.com/adityatelange/hugo-PaperMod/" rel="noopener" target="_blank">PaperMod</a>
</span>
</footer>
<a href="#top" aria-label="go to top" title="Go to Top (Alt + G)" class="top-link" id="top-link" accesskey="g">
<svg xmlns="http://www.w3.org/2000/svg" viewBox="0 0 12 6" fill="currentColor">
<path d="M12 6H0l6-6z" />
</svg>
</a>
<script>
let menu = document.getElementById('menu')
if (menu) {
menu.scrollLeft = localStorage.getItem("menu-scroll-position");
menu.onscroll = function () {
localStorage.setItem("menu-scroll-position", menu.scrollLeft);
}
}
document.querySelectorAll('a[href^="#"]').forEach(anchor => {
anchor.addEventListener("click", function (e) {
e.preventDefault();
var id = this.getAttribute("href").substr(1);
if (!window.matchMedia('(prefers-reduced-motion: reduce)').matches) {
document.querySelector(`[id='${decodeURIComponent(id)}']`).scrollIntoView({
behavior: "smooth"
});
} else {
document.querySelector(`[id='${decodeURIComponent(id)}']`).scrollIntoView();
}
if (id === "top") {
history.replaceState(null, null, " ");
} else {
history.pushState(null, null, `#${id}`);
}
});
});
</script>
<script>
var mybutton = document.getElementById("top-link");
window.onscroll = function () {
if (document.body.scrollTop > 800 || document.documentElement.scrollTop > 800) {
mybutton.style.visibility = "visible";
mybutton.style.opacity = "1";
} else {
mybutton.style.visibility = "hidden";
mybutton.style.opacity = "0";
}
};
</script>
<script>
document.getElementById("theme-toggle").addEventListener("click", () => {
if (document.body.className.includes("dark")) {
document.body.classList.remove('dark');
localStorage.setItem("pref-theme", 'light');
} else {
document.body.classList.add('dark');
localStorage.setItem("pref-theme", 'dark');
}
})
</script>
<script>
document.querySelectorAll('pre > code').forEach((codeblock) => {
const container = codeblock.parentNode.parentNode;
const copybutton = document.createElement('button');
copybutton.classList.add('copy-code');
copybutton.innerHTML = '複製';
function copyingDone() {
copybutton.innerHTML = '已複製！';
setTimeout(() => {
copybutton.innerHTML = '複製';
}, 2000);
}
copybutton.addEventListener('click', (cb) => {
if ('clipboard' in navigator) {
navigator.clipboard.writeText(codeblock.textContent);
copyingDone();
return;
}
const range = document.createRange();
range.selectNodeContents(codeblock);
const selection = window.getSelection();
selection.removeAllRanges();
selection.addRange(range);
try {
document.execCommand('copy');
copyingDone();
} catch (e) { };
selection.removeRange(range);
});
if (container.classList.contains("highlight")) {
container.appendChild(copybutton);
} else if (container.parentNode.firstChild == container) {
} else if (codeblock.parentNode.parentNode.parentNode.parentNode.parentNode.nodeName == "TABLE") {
codeblock.parentNode.parentNode.parentNode.parentNode.parentNode.appendChild(copybutton);
} else {
codeblock.parentNode.appendChild(copybutton);
}
});
</script>
</body>
</html>