如果有做出 3Sum 的人，這類題有一套公式，即使用 TwoPointer 的技巧，靠迴圈、加速搜遍數列。
3Sun是選定一個 i(由前往後)，4Sum就多選一個 j(由後往前)，剩下用 l、r，即 TwoPointer，用總和值來決定移動 l 還是 r。
先把數列排序，若 nums[i] + nums[l] + nums[r] + nums[j] > target，則我們要縮小總和，因此讓 r – 1，反則 l + 1，
這使得每次移動都讓總和與目標值靠近。如果跟總和跟目標值相同，記錄組合，然後移動 l 與 r 。
由於不能重複，存放組合的資料型態可以選hash家族，這樣就能有效率的避免有同樣組合被計到二次以上。
又或者將重複的狀況跳過，不僅可加速迴圈，也可以直接用 list 放結果，不用轉換資料型態。
Python(基本)
class Solution:
def fourSum(self, nums: List[int], target: int) -> List[List[int]]:
n = len(nums)
result = set()
nums.sort()
for i in range(n-3):
for j in range(n-1,i+2,-1):
l, r = i+1, j-1
while l < r:
v = nums[i] + nums[l] + nums[r] + nums[j]
if v > target:
r -= 1
elif v < target:
l += 1
else:
result.add((nums[i],nums[l],nums[r],nums[j]))
l += 1
r -= 1
return result
C#
public class Solution {
public IList> FourSum(int[] nums, int target) {
Array.Sort(nums);
int n = nums.Length;
IList> result = new List>();
for(int i = 0; i < n - 3; i++)
{
for(int j = n - 1; j > i + 2; j--)
{
var l = i + 1; var r = j - 1;
while(l < r)
{
var nsum = nums[i] + nums[l] + nums[r] + nums[j];
if(nsum == target)
{
result.Add(new List(){nums[i], nums[l], nums[r], nums[j]});
while(l < r && nums[l] == nums[l+1] && nums[r] == nums[r-1])
{
l++;
r--;
}
l += 1;
r -= 1;
}
else if(nsum > target)
{
r -= 1;
}
else
{
l += 1;
}
}
while(j > i + 2 && nums[j] == nums[j-1]){j--;}
}
while(i < n - 3 && nums[i] == nums[i+1]){i++;}
}
return result;
}
}
不過會發現，Python這樣子的寫法不夠快，有沒有什麼可以加速的條件可用。
例如重複跳過，若接下來找不到目標值，則進入下一個迴圈。這些條件都很好理解，就不多敘述了。
在添加了一些提前中止的條件後，速度可以壓在100ms以內。
Python
class Solution:
def fourSum(self, nums: List[int], target: int) -> List[List[int]]:
n = len(nums)
result = []
nums.sort()
for i in range(n-3):
if( i > 0 and nums[i] == nums[i-1]): continue
if nums[i] * 4 > target: break
for j in range(n-1,i+2,-1):
if(j target:
if curSum + 2 * nums[l] > target: break
r -= 1
elif v < target:
if curSum + 2 * nums[r] < target: break
l += 1
else:
result.append([nums[i],nums[l],nums[r],nums[j]])
while(l < r and nums[l] == nums[l+1] and nums[r] == nums[r-1]):
l += 1
r -= 1
l += 1
r -= 1
return result