Leetcode——四數之和問題

2020-10-25 12:00:43

題目:

給定一個包含 n 個整數的陣列 nums 和一個目標值 target,判斷 nums 中是否存在四個元素 a,b,c 和 d ,使得 a + b + c + d 的值與 target 相等?找出所有滿足條件且不重複的四元組。

注意:
答案中不可以包含重複的四元組。

範例:

給定陣列 nums = [1, 0, -1, 0, -2, 2],和 target = 0。

滿足要求的四元組集合為: [ [-1, 0, 0, 1], [-2, -1, 1, 2], [-2, 0, 0, 2] ]

思路:

  1. 總體思路與之前寫的部落格"三數之和"相差不大,還是排序+雙指標問題。在對nums陣列排序後,不妨設定左節點a,設定左指標初始值b=a+1,右節點d,右指標初始值c=d-1。
  2. 當nums陣列的長度小於4時,直接返回空列表。
  3. 對左節點a與右節點d進行雙巢狀迴圈,目的是在左右指標做移動時,保持左右節點的相對不變性
  4. 當a+b+c+d-target=0時,新增進列表;當a+b+c+d-target<0時,b++;當a+b+c+d-target>0時,c- -。
  5. 同時,要考慮重複值的問題,針對左節點a與右節點d,在迴圈開始時即做出判斷,當左右節點移動後與前一節點相同時,則保持繼續移動:a++,d- -。
  6. 針對左右指標c,d,在每一次進行移動操作後,再次進行判斷是否與前一值相同,是則繼續移動。

程式碼如下:
在這裡插入圖片描述

測試結果:
在這裡插入圖片描述