iT邦幫忙

2025 iThome 鐵人賽

DAY 18
0
自我挑戰組

leetcode系列 第 18

leetcode 18. 4Sum

  • 分享至 

  • xImage
  •  

題目:
Given an array nums of n integers, return an array of all the unique quadruplets [nums[a], nums[b], nums[c], nums[d]] such that:

0 <= a, b, c, d < n
a, b, c, and d are distinct.
nums[a] + nums[b] + nums[c] + nums[d] == target
You may return the answer in any order.

給定一個整數數組nums,n傳回所有唯一四元組的數組, [nums[a], nums[b], nums[c], nums[d]]滿足:

0 <= a, b, c, d < n
a、、、和是不同的b。cd
nums[a] + nums[b] + nums[c] + nums[d] == target
您可以按任意順序返回答案。
https://ithelp.ithome.com.tw/upload/images/20251002/20169340btwopHMICz.png
方法一:排序 + 雙層迴圈 + 雙指針

排序:先對陣列排序,方便去重和雙指針搜尋。

外層兩層迴圈:固定前兩個數 nums[i], nums[j]。

內層雙指針:在 [j+1, n-1] 範圍內找兩個數,使得總和等於目標值。

去重:

外層:i > 0 && nums[i] == nums[i-1] 跳過。

第二層:j > i+1 && nums[j] == nums[j-1] 跳過。

內層:找到解後,要移動 left、right,同時跳過相同數字避免重複答案。


上一篇
leetcode 17. Letter Combinations of a Phone Number
下一篇
leetcode 19. Remove Nth Node From End of List
系列文
leetcode20
圖片
  熱門推薦
圖片
{{ item.channelVendor }} | {{ item.webinarstarted }} |
{{ formatDate(item.duration) }}
直播中

尚未有邦友留言

立即登入留言